LLVM  mainline
InstCombineCompares.cpp
Go to the documentation of this file.
00001 //===- InstCombineCompares.cpp --------------------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the visitICmp and visitFCmp functions.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "InstCombineInternal.h"
00015 #include "llvm/ADT/APSInt.h"
00016 #include "llvm/ADT/SetVector.h"
00017 #include "llvm/ADT/Statistic.h"
00018 #include "llvm/Analysis/ConstantFolding.h"
00019 #include "llvm/Analysis/InstructionSimplify.h"
00020 #include "llvm/Analysis/MemoryBuiltins.h"
00021 #include "llvm/IR/ConstantRange.h"
00022 #include "llvm/IR/DataLayout.h"
00023 #include "llvm/IR/GetElementPtrTypeIterator.h"
00024 #include "llvm/IR/IntrinsicInst.h"
00025 #include "llvm/IR/PatternMatch.h"
00026 #include "llvm/Support/CommandLine.h"
00027 #include "llvm/Support/Debug.h"
00028 #include "llvm/Analysis/TargetLibraryInfo.h"
00029 
00030 using namespace llvm;
00031 using namespace PatternMatch;
00032 
00033 #define DEBUG_TYPE "instcombine"
00034 
00035 // How many times is a select replaced by one of its operands?
00036 STATISTIC(NumSel, "Number of select opts");
00037 
00038 // Initialization Routines
00039 
00040 static ConstantInt *getOne(Constant *C) {
00041   return ConstantInt::get(cast<IntegerType>(C->getType()), 1);
00042 }
00043 
00044 static ConstantInt *ExtractElement(Constant *V, Constant *Idx) {
00045   return cast<ConstantInt>(ConstantExpr::getExtractElement(V, Idx));
00046 }
00047 
00048 static bool HasAddOverflow(ConstantInt *Result,
00049                            ConstantInt *In1, ConstantInt *In2,
00050                            bool IsSigned) {
00051   if (!IsSigned)
00052     return Result->getValue().ult(In1->getValue());
00053 
00054   if (In2->isNegative())
00055     return Result->getValue().sgt(In1->getValue());
00056   return Result->getValue().slt(In1->getValue());
00057 }
00058 
00059 /// AddWithOverflow - Compute Result = In1+In2, returning true if the result
00060 /// overflowed for this type.
00061 static bool AddWithOverflow(Constant *&Result, Constant *In1,
00062                             Constant *In2, bool IsSigned = false) {
00063   Result = ConstantExpr::getAdd(In1, In2);
00064 
00065   if (VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
00066     for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00067       Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
00068       if (HasAddOverflow(ExtractElement(Result, Idx),
00069                          ExtractElement(In1, Idx),
00070                          ExtractElement(In2, Idx),
00071                          IsSigned))
00072         return true;
00073     }
00074     return false;
00075   }
00076 
00077   return HasAddOverflow(cast<ConstantInt>(Result),
00078                         cast<ConstantInt>(In1), cast<ConstantInt>(In2),
00079                         IsSigned);
00080 }
00081 
00082 static bool HasSubOverflow(ConstantInt *Result,
00083                            ConstantInt *In1, ConstantInt *In2,
00084                            bool IsSigned) {
00085   if (!IsSigned)
00086     return Result->getValue().ugt(In1->getValue());
00087 
00088   if (In2->isNegative())
00089     return Result->getValue().slt(In1->getValue());
00090 
00091   return Result->getValue().sgt(In1->getValue());
00092 }
00093 
00094 /// SubWithOverflow - Compute Result = In1-In2, returning true if the result
00095 /// overflowed for this type.
00096 static bool SubWithOverflow(Constant *&Result, Constant *In1,
00097                             Constant *In2, bool IsSigned = false) {
00098   Result = ConstantExpr::getSub(In1, In2);
00099 
00100   if (VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
00101     for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00102       Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
00103       if (HasSubOverflow(ExtractElement(Result, Idx),
00104                          ExtractElement(In1, Idx),
00105                          ExtractElement(In2, Idx),
00106                          IsSigned))
00107         return true;
00108     }
00109     return false;
00110   }
00111 
00112   return HasSubOverflow(cast<ConstantInt>(Result),
00113                         cast<ConstantInt>(In1), cast<ConstantInt>(In2),
00114                         IsSigned);
00115 }
00116 
00117 /// isSignBitCheck - Given an exploded icmp instruction, return true if the
00118 /// comparison only checks the sign bit.  If it only checks the sign bit, set
00119 /// TrueIfSigned if the result of the comparison is true when the input value is
00120 /// signed.
00121 static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS,
00122                            bool &TrueIfSigned) {
00123   switch (pred) {
00124   case ICmpInst::ICMP_SLT:   // True if LHS s< 0
00125     TrueIfSigned = true;
00126     return RHS->isZero();
00127   case ICmpInst::ICMP_SLE:   // True if LHS s<= RHS and RHS == -1
00128     TrueIfSigned = true;
00129     return RHS->isAllOnesValue();
00130   case ICmpInst::ICMP_SGT:   // True if LHS s> -1
00131     TrueIfSigned = false;
00132     return RHS->isAllOnesValue();
00133   case ICmpInst::ICMP_UGT:
00134     // True if LHS u> RHS and RHS == high-bit-mask - 1
00135     TrueIfSigned = true;
00136     return RHS->isMaxValue(true);
00137   case ICmpInst::ICMP_UGE:
00138     // True if LHS u>= RHS and RHS == high-bit-mask (2^7, 2^15, 2^31, etc)
00139     TrueIfSigned = true;
00140     return RHS->getValue().isSignBit();
00141   default:
00142     return false;
00143   }
00144 }
00145 
00146 /// Returns true if the exploded icmp can be expressed as a signed comparison
00147 /// to zero and updates the predicate accordingly.
00148 /// The signedness of the comparison is preserved.
00149 static bool isSignTest(ICmpInst::Predicate &pred, const ConstantInt *RHS) {
00150   if (!ICmpInst::isSigned(pred))
00151     return false;
00152 
00153   if (RHS->isZero())
00154     return ICmpInst::isRelational(pred);
00155 
00156   if (RHS->isOne()) {
00157     if (pred == ICmpInst::ICMP_SLT) {
00158       pred = ICmpInst::ICMP_SLE;
00159       return true;
00160     }
00161   } else if (RHS->isAllOnesValue()) {
00162     if (pred == ICmpInst::ICMP_SGT) {
00163       pred = ICmpInst::ICMP_SGE;
00164       return true;
00165     }
00166   }
00167 
00168   return false;
00169 }
00170 
00171 // isHighOnes - Return true if the constant is of the form 1+0+.
00172 // This is the same as lowones(~X).
00173 static bool isHighOnes(const ConstantInt *CI) {
00174   return (~CI->getValue() + 1).isPowerOf2();
00175 }
00176 
00177 /// ComputeSignedMinMaxValuesFromKnownBits - Given a signed integer type and a
00178 /// set of known zero and one bits, compute the maximum and minimum values that
00179 /// could have the specified known zero and known one bits, returning them in
00180 /// min/max.
00181 static void ComputeSignedMinMaxValuesFromKnownBits(const APInt& KnownZero,
00182                                                    const APInt& KnownOne,
00183                                                    APInt& Min, APInt& Max) {
00184   assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
00185          KnownZero.getBitWidth() == Min.getBitWidth() &&
00186          KnownZero.getBitWidth() == Max.getBitWidth() &&
00187          "KnownZero, KnownOne and Min, Max must have equal bitwidth.");
00188   APInt UnknownBits = ~(KnownZero|KnownOne);
00189 
00190   // The minimum value is when all unknown bits are zeros, EXCEPT for the sign
00191   // bit if it is unknown.
00192   Min = KnownOne;
00193   Max = KnownOne|UnknownBits;
00194 
00195   if (UnknownBits.isNegative()) { // Sign bit is unknown
00196     Min.setBit(Min.getBitWidth()-1);
00197     Max.clearBit(Max.getBitWidth()-1);
00198   }
00199 }
00200 
00201 // ComputeUnsignedMinMaxValuesFromKnownBits - Given an unsigned integer type and
00202 // a set of known zero and one bits, compute the maximum and minimum values that
00203 // could have the specified known zero and known one bits, returning them in
00204 // min/max.
00205 static void ComputeUnsignedMinMaxValuesFromKnownBits(const APInt &KnownZero,
00206                                                      const APInt &KnownOne,
00207                                                      APInt &Min, APInt &Max) {
00208   assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
00209          KnownZero.getBitWidth() == Min.getBitWidth() &&
00210          KnownZero.getBitWidth() == Max.getBitWidth() &&
00211          "Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth.");
00212   APInt UnknownBits = ~(KnownZero|KnownOne);
00213 
00214   // The minimum value is when the unknown bits are all zeros.
00215   Min = KnownOne;
00216   // The maximum value is when the unknown bits are all ones.
00217   Max = KnownOne|UnknownBits;
00218 }
00219 
00220 /// FoldCmpLoadFromIndexedGlobal - Called we see this pattern:
00221 ///   cmp pred (load (gep GV, ...)), cmpcst
00222 /// where GV is a global variable with a constant initializer.  Try to simplify
00223 /// this into some simple computation that does not need the load.  For example
00224 /// we can optimize "icmp eq (load (gep "foo", 0, i)), 0" into "icmp eq i, 3".
00225 ///
00226 /// If AndCst is non-null, then the loaded value is masked with that constant
00227 /// before doing the comparison.  This handles cases like "A[i]&4 == 0".
00228 Instruction *InstCombiner::
00229 FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV,
00230                              CmpInst &ICI, ConstantInt *AndCst) {
00231   Constant *Init = GV->getInitializer();
00232   if (!isa<ConstantArray>(Init) && !isa<ConstantDataArray>(Init))
00233     return nullptr;
00234 
00235   uint64_t ArrayElementCount = Init->getType()->getArrayNumElements();
00236   if (ArrayElementCount > 1024) return nullptr; // Don't blow up on huge arrays.
00237 
00238   // There are many forms of this optimization we can handle, for now, just do
00239   // the simple index into a single-dimensional array.
00240   //
00241   // Require: GEP GV, 0, i {{, constant indices}}
00242   if (GEP->getNumOperands() < 3 ||
00243       !isa<ConstantInt>(GEP->getOperand(1)) ||
00244       !cast<ConstantInt>(GEP->getOperand(1))->isZero() ||
00245       isa<Constant>(GEP->getOperand(2)))
00246     return nullptr;
00247 
00248   // Check that indices after the variable are constants and in-range for the
00249   // type they index.  Collect the indices.  This is typically for arrays of
00250   // structs.
00251   SmallVector<unsigned, 4> LaterIndices;
00252 
00253   Type *EltTy = Init->getType()->getArrayElementType();
00254   for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) {
00255     ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
00256     if (!Idx) return nullptr;  // Variable index.
00257 
00258     uint64_t IdxVal = Idx->getZExtValue();
00259     if ((unsigned)IdxVal != IdxVal) return nullptr; // Too large array index.
00260 
00261     if (StructType *STy = dyn_cast<StructType>(EltTy))
00262       EltTy = STy->getElementType(IdxVal);
00263     else if (ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
00264       if (IdxVal >= ATy->getNumElements()) return nullptr;
00265       EltTy = ATy->getElementType();
00266     } else {
00267       return nullptr; // Unknown type.
00268     }
00269 
00270     LaterIndices.push_back(IdxVal);
00271   }
00272 
00273   enum { Overdefined = -3, Undefined = -2 };
00274 
00275   // Variables for our state machines.
00276 
00277   // FirstTrueElement/SecondTrueElement - Used to emit a comparison of the form
00278   // "i == 47 | i == 87", where 47 is the first index the condition is true for,
00279   // and 87 is the second (and last) index.  FirstTrueElement is -2 when
00280   // undefined, otherwise set to the first true element.  SecondTrueElement is
00281   // -2 when undefined, -3 when overdefined and >= 0 when that index is true.
00282   int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
00283 
00284   // FirstFalseElement/SecondFalseElement - Used to emit a comparison of the
00285   // form "i != 47 & i != 87".  Same state transitions as for true elements.
00286   int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
00287 
00288   /// TrueRangeEnd/FalseRangeEnd - In conjunction with First*Element, these
00289   /// define a state machine that triggers for ranges of values that the index
00290   /// is true or false for.  This triggers on things like "abbbbc"[i] == 'b'.
00291   /// This is -2 when undefined, -3 when overdefined, and otherwise the last
00292   /// index in the range (inclusive).  We use -2 for undefined here because we
00293   /// use relative comparisons and don't want 0-1 to match -1.
00294   int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
00295 
00296   // MagicBitvector - This is a magic bitvector where we set a bit if the
00297   // comparison is true for element 'i'.  If there are 64 elements or less in
00298   // the array, this will fully represent all the comparison results.
00299   uint64_t MagicBitvector = 0;
00300 
00301   // Scan the array and see if one of our patterns matches.
00302   Constant *CompareRHS = cast<Constant>(ICI.getOperand(1));
00303   for (unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
00304     Constant *Elt = Init->getAggregateElement(i);
00305     if (!Elt) return nullptr;
00306 
00307     // If this is indexing an array of structures, get the structure element.
00308     if (!LaterIndices.empty())
00309       Elt = ConstantExpr::getExtractValue(Elt, LaterIndices);
00310 
00311     // If the element is masked, handle it.
00312     if (AndCst) Elt = ConstantExpr::getAnd(Elt, AndCst);
00313 
00314     // Find out if the comparison would be true or false for the i'th element.
00315     Constant *C = ConstantFoldCompareInstOperands(ICI.getPredicate(), Elt,
00316                                                   CompareRHS, DL, TLI);
00317     // If the result is undef for this element, ignore it.
00318     if (isa<UndefValue>(C)) {
00319       // Extend range state machines to cover this element in case there is an
00320       // undef in the middle of the range.
00321       if (TrueRangeEnd == (int)i-1)
00322         TrueRangeEnd = i;
00323       if (FalseRangeEnd == (int)i-1)
00324         FalseRangeEnd = i;
00325       continue;
00326     }
00327 
00328     // If we can't compute the result for any of the elements, we have to give
00329     // up evaluating the entire conditional.
00330     if (!isa<ConstantInt>(C)) return nullptr;
00331 
00332     // Otherwise, we know if the comparison is true or false for this element,
00333     // update our state machines.
00334     bool IsTrueForElt = !cast<ConstantInt>(C)->isZero();
00335 
00336     // State machine for single/double/range index comparison.
00337     if (IsTrueForElt) {
00338       // Update the TrueElement state machine.
00339       if (FirstTrueElement == Undefined)
00340         FirstTrueElement = TrueRangeEnd = i;  // First true element.
00341       else {
00342         // Update double-compare state machine.
00343         if (SecondTrueElement == Undefined)
00344           SecondTrueElement = i;
00345         else
00346           SecondTrueElement = Overdefined;
00347 
00348         // Update range state machine.
00349         if (TrueRangeEnd == (int)i-1)
00350           TrueRangeEnd = i;
00351         else
00352           TrueRangeEnd = Overdefined;
00353       }
00354     } else {
00355       // Update the FalseElement state machine.
00356       if (FirstFalseElement == Undefined)
00357         FirstFalseElement = FalseRangeEnd = i; // First false element.
00358       else {
00359         // Update double-compare state machine.
00360         if (SecondFalseElement == Undefined)
00361           SecondFalseElement = i;
00362         else
00363           SecondFalseElement = Overdefined;
00364 
00365         // Update range state machine.
00366         if (FalseRangeEnd == (int)i-1)
00367           FalseRangeEnd = i;
00368         else
00369           FalseRangeEnd = Overdefined;
00370       }
00371     }
00372 
00373     // If this element is in range, update our magic bitvector.
00374     if (i < 64 && IsTrueForElt)
00375       MagicBitvector |= 1ULL << i;
00376 
00377     // If all of our states become overdefined, bail out early.  Since the
00378     // predicate is expensive, only check it every 8 elements.  This is only
00379     // really useful for really huge arrays.
00380     if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
00381         SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
00382         FalseRangeEnd == Overdefined)
00383       return nullptr;
00384   }
00385 
00386   // Now that we've scanned the entire array, emit our new comparison(s).  We
00387   // order the state machines in complexity of the generated code.
00388   Value *Idx = GEP->getOperand(2);
00389 
00390   // If the index is larger than the pointer size of the target, truncate the
00391   // index down like the GEP would do implicitly.  We don't have to do this for
00392   // an inbounds GEP because the index can't be out of range.
00393   if (!GEP->isInBounds()) {
00394     Type *IntPtrTy = DL.getIntPtrType(GEP->getType());
00395     unsigned PtrSize = IntPtrTy->getIntegerBitWidth();
00396     if (Idx->getType()->getPrimitiveSizeInBits() > PtrSize)
00397       Idx = Builder->CreateTrunc(Idx, IntPtrTy);
00398   }
00399 
00400   // If the comparison is only true for one or two elements, emit direct
00401   // comparisons.
00402   if (SecondTrueElement != Overdefined) {
00403     // None true -> false.
00404     if (FirstTrueElement == Undefined)
00405       return ReplaceInstUsesWith(ICI, Builder->getFalse());
00406 
00407     Value *FirstTrueIdx = ConstantInt::get(Idx->getType(), FirstTrueElement);
00408 
00409     // True for one element -> 'i == 47'.
00410     if (SecondTrueElement == Undefined)
00411       return new ICmpInst(ICmpInst::ICMP_EQ, Idx, FirstTrueIdx);
00412 
00413     // True for two elements -> 'i == 47 | i == 72'.
00414     Value *C1 = Builder->CreateICmpEQ(Idx, FirstTrueIdx);
00415     Value *SecondTrueIdx = ConstantInt::get(Idx->getType(), SecondTrueElement);
00416     Value *C2 = Builder->CreateICmpEQ(Idx, SecondTrueIdx);
00417     return BinaryOperator::CreateOr(C1, C2);
00418   }
00419 
00420   // If the comparison is only false for one or two elements, emit direct
00421   // comparisons.
00422   if (SecondFalseElement != Overdefined) {
00423     // None false -> true.
00424     if (FirstFalseElement == Undefined)
00425       return ReplaceInstUsesWith(ICI, Builder->getTrue());
00426 
00427     Value *FirstFalseIdx = ConstantInt::get(Idx->getType(), FirstFalseElement);
00428 
00429     // False for one element -> 'i != 47'.
00430     if (SecondFalseElement == Undefined)
00431       return new ICmpInst(ICmpInst::ICMP_NE, Idx, FirstFalseIdx);
00432 
00433     // False for two elements -> 'i != 47 & i != 72'.
00434     Value *C1 = Builder->CreateICmpNE(Idx, FirstFalseIdx);
00435     Value *SecondFalseIdx = ConstantInt::get(Idx->getType(),SecondFalseElement);
00436     Value *C2 = Builder->CreateICmpNE(Idx, SecondFalseIdx);
00437     return BinaryOperator::CreateAnd(C1, C2);
00438   }
00439 
00440   // If the comparison can be replaced with a range comparison for the elements
00441   // where it is true, emit the range check.
00442   if (TrueRangeEnd != Overdefined) {
00443     assert(TrueRangeEnd != FirstTrueElement && "Should emit single compare");
00444 
00445     // Generate (i-FirstTrue) <u (TrueRangeEnd-FirstTrue+1).
00446     if (FirstTrueElement) {
00447       Value *Offs = ConstantInt::get(Idx->getType(), -FirstTrueElement);
00448       Idx = Builder->CreateAdd(Idx, Offs);
00449     }
00450 
00451     Value *End = ConstantInt::get(Idx->getType(),
00452                                   TrueRangeEnd-FirstTrueElement+1);
00453     return new ICmpInst(ICmpInst::ICMP_ULT, Idx, End);
00454   }
00455 
00456   // False range check.
00457   if (FalseRangeEnd != Overdefined) {
00458     assert(FalseRangeEnd != FirstFalseElement && "Should emit single compare");
00459     // Generate (i-FirstFalse) >u (FalseRangeEnd-FirstFalse).
00460     if (FirstFalseElement) {
00461       Value *Offs = ConstantInt::get(Idx->getType(), -FirstFalseElement);
00462       Idx = Builder->CreateAdd(Idx, Offs);
00463     }
00464 
00465     Value *End = ConstantInt::get(Idx->getType(),
00466                                   FalseRangeEnd-FirstFalseElement);
00467     return new ICmpInst(ICmpInst::ICMP_UGT, Idx, End);
00468   }
00469 
00470   // If a magic bitvector captures the entire comparison state
00471   // of this load, replace it with computation that does:
00472   //   ((magic_cst >> i) & 1) != 0
00473   {
00474     Type *Ty = nullptr;
00475 
00476     // Look for an appropriate type:
00477     // - The type of Idx if the magic fits
00478     // - The smallest fitting legal type if we have a DataLayout
00479     // - Default to i32
00480     if (ArrayElementCount <= Idx->getType()->getIntegerBitWidth())
00481       Ty = Idx->getType();
00482     else
00483       Ty = DL.getSmallestLegalIntType(Init->getContext(), ArrayElementCount);
00484 
00485     if (Ty) {
00486       Value *V = Builder->CreateIntCast(Idx, Ty, false);
00487       V = Builder->CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
00488       V = Builder->CreateAnd(ConstantInt::get(Ty, 1), V);
00489       return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0));
00490     }
00491   }
00492 
00493   return nullptr;
00494 }
00495 
00496 /// EvaluateGEPOffsetExpression - Return a value that can be used to compare
00497 /// the *offset* implied by a GEP to zero.  For example, if we have &A[i], we
00498 /// want to return 'i' for "icmp ne i, 0".  Note that, in general, indices can
00499 /// be complex, and scales are involved.  The above expression would also be
00500 /// legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32).
00501 /// This later form is less amenable to optimization though, and we are allowed
00502 /// to generate the first by knowing that pointer arithmetic doesn't overflow.
00503 ///
00504 /// If we can't emit an optimized form for this expression, this returns null.
00505 ///
00506 static Value *EvaluateGEPOffsetExpression(User *GEP, InstCombiner &IC,
00507                                           const DataLayout &DL) {
00508   gep_type_iterator GTI = gep_type_begin(GEP);
00509 
00510   // Check to see if this gep only has a single variable index.  If so, and if
00511   // any constant indices are a multiple of its scale, then we can compute this
00512   // in terms of the scale of the variable index.  For example, if the GEP
00513   // implies an offset of "12 + i*4", then we can codegen this as "3 + i",
00514   // because the expression will cross zero at the same point.
00515   unsigned i, e = GEP->getNumOperands();
00516   int64_t Offset = 0;
00517   for (i = 1; i != e; ++i, ++GTI) {
00518     if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
00519       // Compute the aggregate offset of constant indices.
00520       if (CI->isZero()) continue;
00521 
00522       // Handle a struct index, which adds its field offset to the pointer.
00523       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
00524         Offset += DL.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
00525       } else {
00526         uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType());
00527         Offset += Size*CI->getSExtValue();
00528       }
00529     } else {
00530       // Found our variable index.
00531       break;
00532     }
00533   }
00534 
00535   // If there are no variable indices, we must have a constant offset, just
00536   // evaluate it the general way.
00537   if (i == e) return nullptr;
00538 
00539   Value *VariableIdx = GEP->getOperand(i);
00540   // Determine the scale factor of the variable element.  For example, this is
00541   // 4 if the variable index is into an array of i32.
00542   uint64_t VariableScale = DL.getTypeAllocSize(GTI.getIndexedType());
00543 
00544   // Verify that there are no other variable indices.  If so, emit the hard way.
00545   for (++i, ++GTI; i != e; ++i, ++GTI) {
00546     ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i));
00547     if (!CI) return nullptr;
00548 
00549     // Compute the aggregate offset of constant indices.
00550     if (CI->isZero()) continue;
00551 
00552     // Handle a struct index, which adds its field offset to the pointer.
00553     if (StructType *STy = dyn_cast<StructType>(*GTI)) {
00554       Offset += DL.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
00555     } else {
00556       uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType());
00557       Offset += Size*CI->getSExtValue();
00558     }
00559   }
00560 
00561   // Okay, we know we have a single variable index, which must be a
00562   // pointer/array/vector index.  If there is no offset, life is simple, return
00563   // the index.
00564   Type *IntPtrTy = DL.getIntPtrType(GEP->getOperand(0)->getType());
00565   unsigned IntPtrWidth = IntPtrTy->getIntegerBitWidth();
00566   if (Offset == 0) {
00567     // Cast to intptrty in case a truncation occurs.  If an extension is needed,
00568     // we don't need to bother extending: the extension won't affect where the
00569     // computation crosses zero.
00570     if (VariableIdx->getType()->getPrimitiveSizeInBits() > IntPtrWidth) {
00571       VariableIdx = IC.Builder->CreateTrunc(VariableIdx, IntPtrTy);
00572     }
00573     return VariableIdx;
00574   }
00575 
00576   // Otherwise, there is an index.  The computation we will do will be modulo
00577   // the pointer size, so get it.
00578   uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
00579 
00580   Offset &= PtrSizeMask;
00581   VariableScale &= PtrSizeMask;
00582 
00583   // To do this transformation, any constant index must be a multiple of the
00584   // variable scale factor.  For example, we can evaluate "12 + 4*i" as "3 + i",
00585   // but we can't evaluate "10 + 3*i" in terms of i.  Check that the offset is a
00586   // multiple of the variable scale.
00587   int64_t NewOffs = Offset / (int64_t)VariableScale;
00588   if (Offset != NewOffs*(int64_t)VariableScale)
00589     return nullptr;
00590 
00591   // Okay, we can do this evaluation.  Start by converting the index to intptr.
00592   if (VariableIdx->getType() != IntPtrTy)
00593     VariableIdx = IC.Builder->CreateIntCast(VariableIdx, IntPtrTy,
00594                                             true /*Signed*/);
00595   Constant *OffsetVal = ConstantInt::get(IntPtrTy, NewOffs);
00596   return IC.Builder->CreateAdd(VariableIdx, OffsetVal, "offset");
00597 }
00598 
00599 /// Returns true if we can rewrite Start as a GEP with pointer Base
00600 /// and some integer offset. The nodes that need to be re-written
00601 /// for this transformation will be added to Explored.
00602 static bool canRewriteGEPAsOffset(Value *Start, Value *Base,
00603                                   const DataLayout &DL,
00604                                   SetVector<Value *> &Explored) {
00605   SmallVector<Value *, 16> WorkList(1, Start);
00606   Explored.insert(Base);
00607 
00608   // The following traversal gives us an order which can be used
00609   // when doing the final transformation. Since in the final
00610   // transformation we create the PHI replacement instructions first,
00611   // we don't have to get them in any particular order.
00612   //
00613   // However, for other instructions we will have to traverse the
00614   // operands of an instruction first, which means that we have to
00615   // do a post-order traversal.
00616   while (!WorkList.empty()) {
00617     SetVector<PHINode *> PHIs;
00618 
00619     while (!WorkList.empty()) {
00620       if (Explored.size() >= 100)
00621         return false;
00622 
00623       Value *V = WorkList.back();
00624 
00625       if (Explored.count(V) != 0) {
00626         WorkList.pop_back();
00627         continue;
00628       }
00629 
00630       if (!isa<IntToPtrInst>(V) && !isa<PtrToIntInst>(V) &&
00631           !isa<GEPOperator>(V) && !isa<PHINode>(V))
00632         // We've found some value that we can't explore which is different from
00633         // the base. Therefore we can't do this transformation.
00634         return false;
00635 
00636       if (isa<IntToPtrInst>(V) || isa<PtrToIntInst>(V)) {
00637         auto *CI = dyn_cast<CastInst>(V);
00638         if (!CI->isNoopCast(DL))
00639           return false;
00640 
00641         if (Explored.count(CI->getOperand(0)) == 0)
00642           WorkList.push_back(CI->getOperand(0));
00643       }
00644 
00645       if (auto *GEP = dyn_cast<GEPOperator>(V)) {
00646         // We're limiting the GEP to having one index. This will preserve
00647         // the original pointer type. We could handle more cases in the
00648         // future.
00649         if (GEP->getNumIndices() != 1 || !GEP->isInBounds() ||
00650             GEP->getType() != Start->getType())
00651           return false;
00652 
00653         if (Explored.count(GEP->getOperand(0)) == 0)
00654           WorkList.push_back(GEP->getOperand(0));
00655       }
00656 
00657       if (WorkList.back() == V) {
00658         WorkList.pop_back();
00659         // We've finished visiting this node, mark it as such.
00660         Explored.insert(V);
00661       }
00662 
00663       if (auto *PN = dyn_cast<PHINode>(V)) {
00664         Explored.insert(PN);
00665         PHIs.insert(PN);
00666       }
00667     }
00668 
00669     // Explore the PHI nodes further.
00670     for (auto *PN : PHIs)
00671       for (Value *Op : PN->incoming_values())
00672         if (Explored.count(Op) == 0)
00673           WorkList.push_back(Op);
00674   }
00675 
00676   // Make sure that we can do this. Since we can't insert GEPs in a basic
00677   // block before a PHI node, we can't easily do this transformation if
00678   // we have PHI node users of transformed instructions.
00679   for (Value *Val : Explored) {
00680     for (Value *Use : Val->uses()) {
00681 
00682       auto *PHI = dyn_cast<PHINode>(Use);
00683       auto *Inst = dyn_cast<Instruction>(Val);
00684 
00685       if (Inst == Base || Inst == PHI || !Inst || !PHI ||
00686           Explored.count(PHI) == 0)
00687         continue;
00688 
00689       if (PHI->getParent() == Inst->getParent())
00690         return false;
00691     }
00692   }
00693   return true;
00694 }
00695 
00696 // Sets the appropriate insert point on Builder where we can add
00697 // a replacement Instruction for V (if that is possible).
00698 static void setInsertionPoint(IRBuilder<> &Builder, Value *V,
00699                               bool Before = true) {
00700   if (auto *PHI = dyn_cast<PHINode>(V)) {
00701     Builder.SetInsertPoint(&*PHI->getParent()->getFirstInsertionPt());
00702     return;
00703   }
00704   if (auto *I = dyn_cast<Instruction>(V)) {
00705     if (!Before)
00706       I = &*std::next(I->getIterator());
00707     Builder.SetInsertPoint(I);
00708     return;
00709   }
00710   if (auto *A = dyn_cast<Argument>(V)) {
00711     // Set the insertion point in the entry block.
00712     BasicBlock &Entry = A->getParent()->getEntryBlock();
00713     Builder.SetInsertPoint(&*Entry.getFirstInsertionPt());
00714     return;
00715   }
00716   // Otherwise, this is a constant and we don't need to set a new
00717   // insertion point.
00718   assert(isa<Constant>(V) && "Setting insertion point for unknown value!");
00719 }
00720 
00721 /// Returns a re-written value of Start as an indexed GEP using Base as a
00722 /// pointer.
00723 static Value *rewriteGEPAsOffset(Value *Start, Value *Base,
00724                                  const DataLayout &DL,
00725                                  SetVector<Value *> &Explored) {
00726   // Perform all the substitutions. This is a bit tricky because we can
00727   // have cycles in our use-def chains.
00728   // 1. Create the PHI nodes without any incoming values.
00729   // 2. Create all the other values.
00730   // 3. Add the edges for the PHI nodes.
00731   // 4. Emit GEPs to get the original pointers.
00732   // 5. Remove the original instructions.
00733   Type *IndexType = IntegerType::get(
00734       Base->getContext(), DL.getPointerTypeSizeInBits(Start->getType()));
00735 
00736   DenseMap<Value *, Value *> NewInsts;
00737   NewInsts[Base] = ConstantInt::getNullValue(IndexType);
00738 
00739   // Create the new PHI nodes, without adding any incoming values.
00740   for (Value *Val : Explored) {
00741     if (Val == Base)
00742       continue;
00743     // Create empty phi nodes. This avoids cyclic dependencies when creating
00744     // the remaining instructions.
00745     if (auto *PHI = dyn_cast<PHINode>(Val))
00746       NewInsts[PHI] = PHINode::Create(IndexType, PHI->getNumIncomingValues(),
00747                                       PHI->getName() + ".idx", PHI);
00748   }
00749   IRBuilder<> Builder(Base->getContext());
00750 
00751   // Create all the other instructions.
00752   for (Value *Val : Explored) {
00753 
00754     if (NewInsts.find(Val) != NewInsts.end())
00755       continue;
00756 
00757     if (auto *CI = dyn_cast<CastInst>(Val)) {
00758       NewInsts[CI] = NewInsts[CI->getOperand(0)];
00759       continue;
00760     }
00761     if (auto *GEP = dyn_cast<GEPOperator>(Val)) {
00762       Value *Index = NewInsts[GEP->getOperand(1)] ? NewInsts[GEP->getOperand(1)]
00763                                                   : GEP->getOperand(1);
00764       setInsertionPoint(Builder, GEP);
00765       // Indices might need to be sign extended. GEPs will magically do
00766       // this, but we need to do it ourselves here.
00767       if (Index->getType()->getScalarSizeInBits() !=
00768           NewInsts[GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
00769         Index = Builder.CreateSExtOrTrunc(
00770             Index, NewInsts[GEP->getOperand(0)]->getType(),
00771             GEP->getOperand(0)->getName() + ".sext");
00772       }
00773 
00774       auto *Op = NewInsts[GEP->getOperand(0)];
00775       if (isa<ConstantInt>(Op) && dyn_cast<ConstantInt>(Op)->isZero())
00776         NewInsts[GEP] = Index;
00777       else
00778         NewInsts[GEP] = Builder.CreateNSWAdd(
00779             Op, Index, GEP->getOperand(0)->getName() + ".add");
00780       continue;
00781     }
00782     if (isa<PHINode>(Val))
00783       continue;
00784 
00785     llvm_unreachable("Unexpected instruction type");
00786   }
00787 
00788   // Add the incoming values to the PHI nodes.
00789   for (Value *Val : Explored) {
00790     if (Val == Base)
00791       continue;
00792     // All the instructions have been created, we can now add edges to the
00793     // phi nodes.
00794     if (auto *PHI = dyn_cast<PHINode>(Val)) {
00795       PHINode *NewPhi = static_cast<PHINode *>(NewInsts[PHI]);
00796       for (unsigned I = 0, E = PHI->getNumIncomingValues(); I < E; ++I) {
00797         Value *NewIncoming = PHI->getIncomingValue(I);
00798 
00799         if (NewInsts.find(NewIncoming) != NewInsts.end())
00800           NewIncoming = NewInsts[NewIncoming];
00801 
00802         NewPhi->addIncoming(NewIncoming, PHI->getIncomingBlock(I));
00803       }
00804     }
00805   }
00806 
00807   for (Value *Val : Explored) {
00808     if (Val == Base)
00809       continue;
00810 
00811     // Depending on the type, for external users we have to emit
00812     // a GEP or a GEP + ptrtoint.
00813     setInsertionPoint(Builder, Val, false);
00814 
00815     // If required, create an inttoptr instruction for Base.
00816     Value *NewBase = Base;
00817     if (!Base->getType()->isPointerTy())
00818       NewBase = Builder.CreateBitOrPointerCast(Base, Start->getType(),
00819                                                Start->getName() + "to.ptr");
00820 
00821     Value *GEP = Builder.CreateInBoundsGEP(
00822         Start->getType()->getPointerElementType(), NewBase,
00823         makeArrayRef(NewInsts[Val]), Val->getName() + ".ptr");
00824 
00825     if (!Val->getType()->isPointerTy()) {
00826       Value *Cast = Builder.CreatePointerCast(GEP, Val->getType(),
00827                                               Val->getName() + ".conv");
00828       GEP = Cast;
00829     }
00830     Val->replaceAllUsesWith(GEP);
00831   }
00832 
00833   return NewInsts[Start];
00834 }
00835 
00836 /// Looks through GEPs, IntToPtrInsts and PtrToIntInsts in order to express
00837 /// the input Value as a constant indexed GEP. Returns a pair containing
00838 /// the GEPs Pointer and Index.
00839 static std::pair<Value *, Value *>
00840 getAsConstantIndexedAddress(Value *V, const DataLayout &DL) {
00841   Type *IndexType = IntegerType::get(V->getContext(),
00842                                      DL.getPointerTypeSizeInBits(V->getType()));
00843 
00844   Constant *Index = ConstantInt::getNullValue(IndexType);
00845   while (true) {
00846     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00847       // We accept only inbouds GEPs here to exclude the possibility of
00848       // overflow.
00849       if (!GEP->isInBounds())
00850         break;
00851       if (GEP->hasAllConstantIndices() && GEP->getNumIndices() == 1 &&
00852           GEP->getType() == V->getType()) {
00853         V = GEP->getOperand(0);
00854         Constant *GEPIndex = static_cast<Constant *>(GEP->getOperand(1));
00855         Index = ConstantExpr::getAdd(
00856             Index, ConstantExpr::getSExtOrBitCast(GEPIndex, IndexType));
00857         continue;
00858       }
00859       break;
00860     }
00861     if (auto *CI = dyn_cast<IntToPtrInst>(V)) {
00862       if (!CI->isNoopCast(DL))
00863         break;
00864       V = CI->getOperand(0);
00865       continue;
00866     }
00867     if (auto *CI = dyn_cast<PtrToIntInst>(V)) {
00868       if (!CI->isNoopCast(DL))
00869         break;
00870       V = CI->getOperand(0);
00871       continue;
00872     }
00873     break;
00874   }
00875   return {V, Index};
00876 }
00877 
00878 // Converts (CMP GEPLHS, RHS) if this change would make RHS a constant.
00879 // We can look through PHIs, GEPs and casts in order to determine a
00880 // common base between GEPLHS and RHS.
00881 static Instruction *transformToIndexedCompare(GEPOperator *GEPLHS, Value *RHS,
00882                                               ICmpInst::Predicate Cond,
00883                                               const DataLayout &DL) {
00884   if (!GEPLHS->hasAllConstantIndices())
00885     return nullptr;
00886 
00887   Value *PtrBase, *Index;
00888   std::tie(PtrBase, Index) = getAsConstantIndexedAddress(GEPLHS, DL);
00889 
00890   // The set of nodes that will take part in this transformation.
00891   SetVector<Value *> Nodes;
00892 
00893   if (!canRewriteGEPAsOffset(RHS, PtrBase, DL, Nodes))
00894     return nullptr;
00895 
00896   // We know we can re-write this as
00897   //  ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)
00898   // Since we've only looked through inbouds GEPs we know that we
00899   // can't have overflow on either side. We can therefore re-write
00900   // this as:
00901   //   OFFSET1 cmp OFFSET2
00902   Value *NewRHS = rewriteGEPAsOffset(RHS, PtrBase, DL, Nodes);
00903 
00904   // RewriteGEPAsOffset has replaced RHS and all of its uses with a re-written
00905   // GEP having PtrBase as the pointer base, and has returned in NewRHS the
00906   // offset. Since Index is the offset of LHS to the base pointer, we will now
00907   // compare the offsets instead of comparing the pointers.
00908   return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Index, NewRHS);
00909 }
00910 
00911 /// FoldGEPICmp - Fold comparisons between a GEP instruction and something
00912 /// else.  At this point we know that the GEP is on the LHS of the comparison.
00913 Instruction *InstCombiner::FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
00914                                        ICmpInst::Predicate Cond,
00915                                        Instruction &I) {
00916   // Don't transform signed compares of GEPs into index compares. Even if the
00917   // GEP is inbounds, the final add of the base pointer can have signed overflow
00918   // and would change the result of the icmp.
00919   // e.g. "&foo[0] <s &foo[1]" can't be folded to "true" because "foo" could be
00920   // the maximum signed value for the pointer type.
00921   if (ICmpInst::isSigned(Cond))
00922     return nullptr;
00923 
00924   // Look through bitcasts and addrspacecasts. We do not however want to remove
00925   // 0 GEPs.
00926   if (!isa<GetElementPtrInst>(RHS))
00927     RHS = RHS->stripPointerCasts();
00928 
00929   Value *PtrBase = GEPLHS->getOperand(0);
00930   if (PtrBase == RHS && GEPLHS->isInBounds()) {
00931     // ((gep Ptr, OFFSET) cmp Ptr)   ---> (OFFSET cmp 0).
00932     // This transformation (ignoring the base and scales) is valid because we
00933     // know pointers can't overflow since the gep is inbounds.  See if we can
00934     // output an optimized form.
00935     Value *Offset = EvaluateGEPOffsetExpression(GEPLHS, *this, DL);
00936 
00937     // If not, synthesize the offset the hard way.
00938     if (!Offset)
00939       Offset = EmitGEPOffset(GEPLHS);
00940     return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Offset,
00941                         Constant::getNullValue(Offset->getType()));
00942   } else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) {
00943     // If the base pointers are different, but the indices are the same, just
00944     // compare the base pointer.
00945     if (PtrBase != GEPRHS->getOperand(0)) {
00946       bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands();
00947       IndicesTheSame &= GEPLHS->getOperand(0)->getType() ==
00948                         GEPRHS->getOperand(0)->getType();
00949       if (IndicesTheSame)
00950         for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
00951           if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
00952             IndicesTheSame = false;
00953             break;
00954           }
00955 
00956       // If all indices are the same, just compare the base pointers.
00957       if (IndicesTheSame)
00958         return new ICmpInst(Cond, GEPLHS->getOperand(0), GEPRHS->getOperand(0));
00959 
00960       // If we're comparing GEPs with two base pointers that only differ in type
00961       // and both GEPs have only constant indices or just one use, then fold
00962       // the compare with the adjusted indices.
00963       if (GEPLHS->isInBounds() && GEPRHS->isInBounds() &&
00964           (GEPLHS->hasAllConstantIndices() || GEPLHS->hasOneUse()) &&
00965           (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
00966           PtrBase->stripPointerCasts() ==
00967               GEPRHS->getOperand(0)->stripPointerCasts()) {
00968         Value *LOffset = EmitGEPOffset(GEPLHS);
00969         Value *ROffset = EmitGEPOffset(GEPRHS);
00970 
00971         // If we looked through an addrspacecast between different sized address
00972         // spaces, the LHS and RHS pointers are different sized
00973         // integers. Truncate to the smaller one.
00974         Type *LHSIndexTy = LOffset->getType();
00975         Type *RHSIndexTy = ROffset->getType();
00976         if (LHSIndexTy != RHSIndexTy) {
00977           if (LHSIndexTy->getPrimitiveSizeInBits() <
00978               RHSIndexTy->getPrimitiveSizeInBits()) {
00979             ROffset = Builder->CreateTrunc(ROffset, LHSIndexTy);
00980           } else
00981             LOffset = Builder->CreateTrunc(LOffset, RHSIndexTy);
00982         }
00983 
00984         Value *Cmp = Builder->CreateICmp(ICmpInst::getSignedPredicate(Cond),
00985                                          LOffset, ROffset);
00986         return ReplaceInstUsesWith(I, Cmp);
00987       }
00988 
00989       // Otherwise, the base pointers are different and the indices are
00990       // different. Try convert this to an indexed compare by looking through
00991       // PHIs/casts.
00992       return transformToIndexedCompare(GEPLHS, RHS, Cond, DL);
00993     }
00994 
00995     // If one of the GEPs has all zero indices, recurse.
00996     if (GEPLHS->hasAllZeroIndices())
00997       return FoldGEPICmp(GEPRHS, GEPLHS->getOperand(0),
00998                          ICmpInst::getSwappedPredicate(Cond), I);
00999 
01000     // If the other GEP has all zero indices, recurse.
01001     if (GEPRHS->hasAllZeroIndices())
01002       return FoldGEPICmp(GEPLHS, GEPRHS->getOperand(0), Cond, I);
01003 
01004     bool GEPsInBounds = GEPLHS->isInBounds() && GEPRHS->isInBounds();
01005     if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) {
01006       // If the GEPs only differ by one index, compare it.
01007       unsigned NumDifferences = 0;  // Keep track of # differences.
01008       unsigned DiffOperand = 0;     // The operand that differs.
01009       for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
01010         if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
01011           if (GEPLHS->getOperand(i)->getType()->getPrimitiveSizeInBits() !=
01012                    GEPRHS->getOperand(i)->getType()->getPrimitiveSizeInBits()) {
01013             // Irreconcilable differences.
01014             NumDifferences = 2;
01015             break;
01016           } else {
01017             if (NumDifferences++) break;
01018             DiffOperand = i;
01019           }
01020         }
01021 
01022       if (NumDifferences == 0)   // SAME GEP?
01023         return ReplaceInstUsesWith(I, // No comparison is needed here.
01024                              Builder->getInt1(ICmpInst::isTrueWhenEqual(Cond)));
01025 
01026       else if (NumDifferences == 1 && GEPsInBounds) {
01027         Value *LHSV = GEPLHS->getOperand(DiffOperand);
01028         Value *RHSV = GEPRHS->getOperand(DiffOperand);
01029         // Make sure we do a signed comparison here.
01030         return new ICmpInst(ICmpInst::getSignedPredicate(Cond), LHSV, RHSV);
01031       }
01032     }
01033 
01034     // Only lower this if the icmp is the only user of the GEP or if we expect
01035     // the result to fold to a constant!
01036     if (GEPsInBounds && (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
01037         (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
01038       // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)  --->  (OFFSET1 cmp OFFSET2)
01039       Value *L = EmitGEPOffset(GEPLHS);
01040       Value *R = EmitGEPOffset(GEPRHS);
01041       return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R);
01042     }
01043   }
01044 
01045   // Try convert this to an indexed compare by looking through PHIs/casts as a
01046   // last resort.
01047   return transformToIndexedCompare(GEPLHS, RHS, Cond, DL);
01048 }
01049 
01050 Instruction *InstCombiner::FoldAllocaCmp(ICmpInst &ICI, AllocaInst *Alloca,
01051                                          Value *Other) {
01052   assert(ICI.isEquality() && "Cannot fold non-equality comparison.");
01053 
01054   // It would be tempting to fold away comparisons between allocas and any
01055   // pointer not based on that alloca (e.g. an argument). However, even
01056   // though such pointers cannot alias, they can still compare equal.
01057   //
01058   // But LLVM doesn't specify where allocas get their memory, so if the alloca
01059   // doesn't escape we can argue that it's impossible to guess its value, and we
01060   // can therefore act as if any such guesses are wrong.
01061   //
01062   // The code below checks that the alloca doesn't escape, and that it's only
01063   // used in a comparison once (the current instruction). The
01064   // single-comparison-use condition ensures that we're trivially folding all
01065   // comparisons against the alloca consistently, and avoids the risk of
01066   // erroneously folding a comparison of the pointer with itself.
01067 
01068   unsigned MaxIter = 32; // Break cycles and bound to constant-time.
01069 
01070   SmallVector<Use *, 32> Worklist;
01071   for (Use &U : Alloca->uses()) {
01072     if (Worklist.size() >= MaxIter)
01073       return nullptr;
01074     Worklist.push_back(&U);
01075   }
01076 
01077   unsigned NumCmps = 0;
01078   while (!Worklist.empty()) {
01079     assert(Worklist.size() <= MaxIter);
01080     Use *U = Worklist.pop_back_val();
01081     Value *V = U->getUser();
01082     --MaxIter;
01083 
01084     if (isa<BitCastInst>(V) || isa<GetElementPtrInst>(V) || isa<PHINode>(V) ||
01085         isa<SelectInst>(V)) {
01086       // Track the uses.
01087     } else if (isa<LoadInst>(V)) {
01088       // Loading from the pointer doesn't escape it.
01089       continue;
01090     } else if (auto *SI = dyn_cast<StoreInst>(V)) {
01091       // Storing *to* the pointer is fine, but storing the pointer escapes it.
01092       if (SI->getValueOperand() == U->get())
01093         return nullptr;
01094       continue;
01095     } else if (isa<ICmpInst>(V)) {
01096       if (NumCmps++)
01097         return nullptr; // Found more than one cmp.
01098       continue;
01099     } else if (auto *Intrin = dyn_cast<IntrinsicInst>(V)) {
01100       switch (Intrin->getIntrinsicID()) {
01101         // These intrinsics don't escape or compare the pointer. Memset is safe
01102         // because we don't allow ptrtoint. Memcpy and memmove are safe because
01103         // we don't allow stores, so src cannot point to V.
01104         case Intrinsic::lifetime_start: case Intrinsic::lifetime_end:
01105         case Intrinsic::dbg_declare: case Intrinsic::dbg_value:
01106         case Intrinsic::memcpy: case Intrinsic::memmove: case Intrinsic::memset:
01107           continue;
01108         default:
01109           return nullptr;
01110       }
01111     } else {
01112       return nullptr;
01113     }
01114     for (Use &U : V->uses()) {
01115       if (Worklist.size() >= MaxIter)
01116         return nullptr;
01117       Worklist.push_back(&U);
01118     }
01119   }
01120 
01121   Type *CmpTy = CmpInst::makeCmpResultType(Other->getType());
01122   return ReplaceInstUsesWith(
01123       ICI,
01124       ConstantInt::get(CmpTy, !CmpInst::isTrueWhenEqual(ICI.getPredicate())));
01125 }
01126 
01127 /// FoldICmpAddOpCst - Fold "icmp pred (X+CI), X".
01128 Instruction *InstCombiner::FoldICmpAddOpCst(Instruction &ICI,
01129                                             Value *X, ConstantInt *CI,
01130                                             ICmpInst::Predicate Pred) {
01131   // From this point on, we know that (X+C <= X) --> (X+C < X) because C != 0,
01132   // so the values can never be equal.  Similarly for all other "or equals"
01133   // operators.
01134 
01135   // (X+1) <u X        --> X >u (MAXUINT-1)        --> X == 255
01136   // (X+2) <u X        --> X >u (MAXUINT-2)        --> X > 253
01137   // (X+MAXUINT) <u X  --> X >u (MAXUINT-MAXUINT)  --> X != 0
01138   if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) {
01139     Value *R =
01140       ConstantExpr::getSub(ConstantInt::getAllOnesValue(CI->getType()), CI);
01141     return new ICmpInst(ICmpInst::ICMP_UGT, X, R);
01142   }
01143 
01144   // (X+1) >u X        --> X <u (0-1)        --> X != 255
01145   // (X+2) >u X        --> X <u (0-2)        --> X <u 254
01146   // (X+MAXUINT) >u X  --> X <u (0-MAXUINT)  --> X <u 1  --> X == 0
01147   if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE)
01148     return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantExpr::getNeg(CI));
01149 
01150   unsigned BitWidth = CI->getType()->getPrimitiveSizeInBits();
01151   ConstantInt *SMax = ConstantInt::get(X->getContext(),
01152                                        APInt::getSignedMaxValue(BitWidth));
01153 
01154   // (X+ 1) <s X       --> X >s (MAXSINT-1)          --> X == 127
01155   // (X+ 2) <s X       --> X >s (MAXSINT-2)          --> X >s 125
01156   // (X+MAXSINT) <s X  --> X >s (MAXSINT-MAXSINT)    --> X >s 0
01157   // (X+MINSINT) <s X  --> X >s (MAXSINT-MINSINT)    --> X >s -1
01158   // (X+ -2) <s X      --> X >s (MAXSINT- -2)        --> X >s 126
01159   // (X+ -1) <s X      --> X >s (MAXSINT- -1)        --> X != 127
01160   if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
01161     return new ICmpInst(ICmpInst::ICMP_SGT, X, ConstantExpr::getSub(SMax, CI));
01162 
01163   // (X+ 1) >s X       --> X <s (MAXSINT-(1-1))       --> X != 127
01164   // (X+ 2) >s X       --> X <s (MAXSINT-(2-1))       --> X <s 126
01165   // (X+MAXSINT) >s X  --> X <s (MAXSINT-(MAXSINT-1)) --> X <s 1
01166   // (X+MINSINT) >s X  --> X <s (MAXSINT-(MINSINT-1)) --> X <s -2
01167   // (X+ -2) >s X      --> X <s (MAXSINT-(-2-1))      --> X <s -126
01168   // (X+ -1) >s X      --> X <s (MAXSINT-(-1-1))      --> X == -128
01169 
01170   assert(Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE);
01171   Constant *C = Builder->getInt(CI->getValue()-1);
01172   return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantExpr::getSub(SMax, C));
01173 }
01174 
01175 /// FoldICmpDivCst - Fold "icmp pred, ([su]div X, DivRHS), CmpRHS" where DivRHS
01176 /// and CmpRHS are both known to be integer constants.
01177 Instruction *InstCombiner::FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
01178                                           ConstantInt *DivRHS) {
01179   ConstantInt *CmpRHS = cast<ConstantInt>(ICI.getOperand(1));
01180   const APInt &CmpRHSV = CmpRHS->getValue();
01181 
01182   // FIXME: If the operand types don't match the type of the divide
01183   // then don't attempt this transform. The code below doesn't have the
01184   // logic to deal with a signed divide and an unsigned compare (and
01185   // vice versa). This is because (x /s C1) <s C2  produces different
01186   // results than (x /s C1) <u C2 or (x /u C1) <s C2 or even
01187   // (x /u C1) <u C2.  Simply casting the operands and result won't
01188   // work. :(  The if statement below tests that condition and bails
01189   // if it finds it.
01190   bool DivIsSigned = DivI->getOpcode() == Instruction::SDiv;
01191   if (!ICI.isEquality() && DivIsSigned != ICI.isSigned())
01192     return nullptr;
01193   if (DivRHS->isZero())
01194     return nullptr; // The ProdOV computation fails on divide by zero.
01195   if (DivIsSigned && DivRHS->isAllOnesValue())
01196     return nullptr; // The overflow computation also screws up here
01197   if (DivRHS->isOne()) {
01198     // This eliminates some funny cases with INT_MIN.
01199     ICI.setOperand(0, DivI->getOperand(0));   // X/1 == X.
01200     return &ICI;
01201   }
01202 
01203   // Compute Prod = CI * DivRHS. We are essentially solving an equation
01204   // of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and
01205   // C2 (CI). By solving for X we can turn this into a range check
01206   // instead of computing a divide.
01207   Constant *Prod = ConstantExpr::getMul(CmpRHS, DivRHS);
01208 
01209   // Determine if the product overflows by seeing if the product is
01210   // not equal to the divide. Make sure we do the same kind of divide
01211   // as in the LHS instruction that we're folding.
01212   bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) :
01213                  ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS;
01214 
01215   // Get the ICmp opcode
01216   ICmpInst::Predicate Pred = ICI.getPredicate();
01217 
01218   /// If the division is known to be exact, then there is no remainder from the
01219   /// divide, so the covered range size is unit, otherwise it is the divisor.
01220   ConstantInt *RangeSize = DivI->isExact() ? getOne(Prod) : DivRHS;
01221 
01222   // Figure out the interval that is being checked.  For example, a comparison
01223   // like "X /u 5 == 0" is really checking that X is in the interval [0, 5).
01224   // Compute this interval based on the constants involved and the signedness of
01225   // the compare/divide.  This computes a half-open interval, keeping track of
01226   // whether either value in the interval overflows.  After analysis each
01227   // overflow variable is set to 0 if it's corresponding bound variable is valid
01228   // -1 if overflowed off the bottom end, or +1 if overflowed off the top end.
01229   int LoOverflow = 0, HiOverflow = 0;
01230   Constant *LoBound = nullptr, *HiBound = nullptr;
01231 
01232   if (!DivIsSigned) {  // udiv
01233     // e.g. X/5 op 3  --> [15, 20)
01234     LoBound = Prod;
01235     HiOverflow = LoOverflow = ProdOV;
01236     if (!HiOverflow) {
01237       // If this is not an exact divide, then many values in the range collapse
01238       // to the same result value.
01239       HiOverflow = AddWithOverflow(HiBound, LoBound, RangeSize, false);
01240     }
01241   } else if (DivRHS->getValue().isStrictlyPositive()) { // Divisor is > 0.
01242     if (CmpRHSV == 0) {       // (X / pos) op 0
01243       // Can't overflow.  e.g.  X/2 op 0 --> [-1, 2)
01244       LoBound = ConstantExpr::getNeg(SubOne(RangeSize));
01245       HiBound = RangeSize;
01246     } else if (CmpRHSV.isStrictlyPositive()) {   // (X / pos) op pos
01247       LoBound = Prod;     // e.g.   X/5 op 3 --> [15, 20)
01248       HiOverflow = LoOverflow = ProdOV;
01249       if (!HiOverflow)
01250         HiOverflow = AddWithOverflow(HiBound, Prod, RangeSize, true);
01251     } else {                       // (X / pos) op neg
01252       // e.g. X/5 op -3  --> [-15-4, -15+1) --> [-19, -14)
01253       HiBound = AddOne(Prod);
01254       LoOverflow = HiOverflow = ProdOV ? -1 : 0;
01255       if (!LoOverflow) {
01256         ConstantInt *DivNeg =cast<ConstantInt>(ConstantExpr::getNeg(RangeSize));
01257         LoOverflow = AddWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0;
01258       }
01259     }
01260   } else if (DivRHS->isNegative()) { // Divisor is < 0.
01261     if (DivI->isExact())
01262       RangeSize = cast<ConstantInt>(ConstantExpr::getNeg(RangeSize));
01263     if (CmpRHSV == 0) {       // (X / neg) op 0
01264       // e.g. X/-5 op 0  --> [-4, 5)
01265       LoBound = AddOne(RangeSize);
01266       HiBound = cast<ConstantInt>(ConstantExpr::getNeg(RangeSize));
01267       if (HiBound == DivRHS) {     // -INTMIN = INTMIN
01268         HiOverflow = 1;            // [INTMIN+1, overflow)
01269         HiBound = nullptr;         // e.g. X/INTMIN = 0 --> X > INTMIN
01270       }
01271     } else if (CmpRHSV.isStrictlyPositive()) {   // (X / neg) op pos
01272       // e.g. X/-5 op 3  --> [-19, -14)
01273       HiBound = AddOne(Prod);
01274       HiOverflow = LoOverflow = ProdOV ? -1 : 0;
01275       if (!LoOverflow)
01276         LoOverflow = AddWithOverflow(LoBound, HiBound, RangeSize, true) ? -1:0;
01277     } else {                       // (X / neg) op neg
01278       LoBound = Prod;       // e.g. X/-5 op -3  --> [15, 20)
01279       LoOverflow = HiOverflow = ProdOV;
01280       if (!HiOverflow)
01281         HiOverflow = SubWithOverflow(HiBound, Prod, RangeSize, true);
01282     }
01283 
01284     // Dividing by a negative swaps the condition.  LT <-> GT
01285     Pred = ICmpInst::getSwappedPredicate(Pred);
01286   }
01287 
01288   Value *X = DivI->getOperand(0);
01289   switch (Pred) {
01290   default: llvm_unreachable("Unhandled icmp opcode!");
01291   case ICmpInst::ICMP_EQ:
01292     if (LoOverflow && HiOverflow)
01293       return ReplaceInstUsesWith(ICI, Builder->getFalse());
01294     if (HiOverflow)
01295       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
01296                           ICmpInst::ICMP_UGE, X, LoBound);
01297     if (LoOverflow)
01298       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
01299                           ICmpInst::ICMP_ULT, X, HiBound);
01300     return ReplaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound,
01301                                                     DivIsSigned, true));
01302   case ICmpInst::ICMP_NE:
01303     if (LoOverflow && HiOverflow)
01304       return ReplaceInstUsesWith(ICI, Builder->getTrue());
01305     if (HiOverflow)
01306       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
01307                           ICmpInst::ICMP_ULT, X, LoBound);
01308     if (LoOverflow)
01309       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
01310                           ICmpInst::ICMP_UGE, X, HiBound);
01311     return ReplaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound,
01312                                                     DivIsSigned, false));
01313   case ICmpInst::ICMP_ULT:
01314   case ICmpInst::ICMP_SLT:
01315     if (LoOverflow == +1)   // Low bound is greater than input range.
01316       return ReplaceInstUsesWith(ICI, Builder->getTrue());
01317     if (LoOverflow == -1)   // Low bound is less than input range.
01318       return ReplaceInstUsesWith(ICI, Builder->getFalse());
01319     return new ICmpInst(Pred, X, LoBound);
01320   case ICmpInst::ICMP_UGT:
01321   case ICmpInst::ICMP_SGT:
01322     if (HiOverflow == +1)       // High bound greater than input range.
01323       return ReplaceInstUsesWith(ICI, Builder->getFalse());
01324     if (HiOverflow == -1)       // High bound less than input range.
01325       return ReplaceInstUsesWith(ICI, Builder->getTrue());
01326     if (Pred == ICmpInst::ICMP_UGT)
01327       return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound);
01328     return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound);
01329   }
01330 }
01331 
01332 /// FoldICmpShrCst - Handle "icmp(([al]shr X, cst1), cst2)".
01333 Instruction *InstCombiner::FoldICmpShrCst(ICmpInst &ICI, BinaryOperator *Shr,
01334                                           ConstantInt *ShAmt) {
01335   const APInt &CmpRHSV = cast<ConstantInt>(ICI.getOperand(1))->getValue();
01336 
01337   // Check that the shift amount is in range.  If not, don't perform
01338   // undefined shifts.  When the shift is visited it will be
01339   // simplified.
01340   uint32_t TypeBits = CmpRHSV.getBitWidth();
01341   uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
01342   if (ShAmtVal >= TypeBits || ShAmtVal == 0)
01343     return nullptr;
01344 
01345   if (!ICI.isEquality()) {
01346     // If we have an unsigned comparison and an ashr, we can't simplify this.
01347     // Similarly for signed comparisons with lshr.
01348     if (ICI.isSigned() != (Shr->getOpcode() == Instruction::AShr))
01349       return nullptr;
01350 
01351     // Otherwise, all lshr and most exact ashr's are equivalent to a udiv/sdiv
01352     // by a power of 2.  Since we already have logic to simplify these,
01353     // transform to div and then simplify the resultant comparison.
01354     if (Shr->getOpcode() == Instruction::AShr &&
01355         (!Shr->isExact() || ShAmtVal == TypeBits - 1))
01356       return nullptr;
01357 
01358     // Revisit the shift (to delete it).
01359     Worklist.Add(Shr);
01360 
01361     Constant *DivCst =
01362       ConstantInt::get(Shr->getType(), APInt::getOneBitSet(TypeBits, ShAmtVal));
01363 
01364     Value *Tmp =
01365       Shr->getOpcode() == Instruction::AShr ?
01366       Builder->CreateSDiv(Shr->getOperand(0), DivCst, "", Shr->isExact()) :
01367       Builder->CreateUDiv(Shr->getOperand(0), DivCst, "", Shr->isExact());
01368 
01369     ICI.setOperand(0, Tmp);
01370 
01371     // If the builder folded the binop, just return it.
01372     BinaryOperator *TheDiv = dyn_cast<BinaryOperator>(Tmp);
01373     if (!TheDiv)
01374       return &ICI;
01375 
01376     // Otherwise, fold this div/compare.
01377     assert(TheDiv->getOpcode() == Instruction::SDiv ||
01378            TheDiv->getOpcode() == Instruction::UDiv);
01379 
01380     Instruction *Res = FoldICmpDivCst(ICI, TheDiv, cast<ConstantInt>(DivCst));
01381     assert(Res && "This div/cst should have folded!");
01382     return Res;
01383   }
01384 
01385   // If we are comparing against bits always shifted out, the
01386   // comparison cannot succeed.
01387   APInt Comp = CmpRHSV << ShAmtVal;
01388   ConstantInt *ShiftedCmpRHS = Builder->getInt(Comp);
01389   if (Shr->getOpcode() == Instruction::LShr)
01390     Comp = Comp.lshr(ShAmtVal);
01391   else
01392     Comp = Comp.ashr(ShAmtVal);
01393 
01394   if (Comp != CmpRHSV) { // Comparing against a bit that we know is zero.
01395     bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
01396     Constant *Cst = Builder->getInt1(IsICMP_NE);
01397     return ReplaceInstUsesWith(ICI, Cst);
01398   }
01399 
01400   // Otherwise, check to see if the bits shifted out are known to be zero.
01401   // If so, we can compare against the unshifted value:
01402   //  (X & 4) >> 1 == 2  --> (X & 4) == 4.
01403   if (Shr->hasOneUse() && Shr->isExact())
01404     return new ICmpInst(ICI.getPredicate(), Shr->getOperand(0), ShiftedCmpRHS);
01405 
01406   if (Shr->hasOneUse()) {
01407     // Otherwise strength reduce the shift into an and.
01408     APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal));
01409     Constant *Mask = Builder->getInt(Val);
01410 
01411     Value *And = Builder->CreateAnd(Shr->getOperand(0),
01412                                     Mask, Shr->getName()+".mask");
01413     return new ICmpInst(ICI.getPredicate(), And, ShiftedCmpRHS);
01414   }
01415   return nullptr;
01416 }
01417 
01418 /// FoldICmpCstShrCst - Handle "(icmp eq/ne (ashr/lshr const2, A), const1)" ->
01419 /// (icmp eq/ne A, Log2(const2/const1)) ->
01420 /// (icmp eq/ne A, Log2(const2) - Log2(const1)).
01421 Instruction *InstCombiner::FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
01422                                              ConstantInt *CI1,
01423                                              ConstantInt *CI2) {
01424   assert(I.isEquality() && "Cannot fold icmp gt/lt");
01425 
01426   auto getConstant = [&I, this](bool IsTrue) {
01427     if (I.getPredicate() == I.ICMP_NE)
01428       IsTrue = !IsTrue;
01429     return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), IsTrue));
01430   };
01431 
01432   auto getICmp = [&I](CmpInst::Predicate Pred, Value *LHS, Value *RHS) {
01433     if (I.getPredicate() == I.ICMP_NE)
01434       Pred = CmpInst::getInversePredicate(Pred);
01435     return new ICmpInst(Pred, LHS, RHS);
01436   };
01437 
01438   APInt AP1 = CI1->getValue();
01439   APInt AP2 = CI2->getValue();
01440 
01441   // Don't bother doing any work for cases which InstSimplify handles.
01442   if (AP2 == 0)
01443     return nullptr;
01444   bool IsAShr = isa<AShrOperator>(Op);
01445   if (IsAShr) {
01446     if (AP2.isAllOnesValue())
01447       return nullptr;
01448     if (AP2.isNegative() != AP1.isNegative())
01449       return nullptr;
01450     if (AP2.sgt(AP1))
01451       return nullptr;
01452   }
01453 
01454   if (!AP1)
01455     // 'A' must be large enough to shift out the highest set bit.
01456     return getICmp(I.ICMP_UGT, A,
01457                    ConstantInt::get(A->getType(), AP2.logBase2()));
01458 
01459   if (AP1 == AP2)
01460     return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
01461 
01462   int Shift;
01463   if (IsAShr && AP1.isNegative())
01464     Shift = AP1.countLeadingOnes() - AP2.countLeadingOnes();
01465   else
01466     Shift = AP1.countLeadingZeros() - AP2.countLeadingZeros();
01467 
01468   if (Shift > 0) {
01469     if (IsAShr && AP1 == AP2.ashr(Shift)) {
01470       // There are multiple solutions if we are comparing against -1 and the LHS
01471       // of the ashr is not a power of two.
01472       if (AP1.isAllOnesValue() && !AP2.isPowerOf2())
01473         return getICmp(I.ICMP_UGE, A, ConstantInt::get(A->getType(), Shift));
01474       return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
01475     } else if (AP1 == AP2.lshr(Shift)) {
01476       return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
01477     }
01478   }
01479   // Shifting const2 will never be equal to const1.
01480   return getConstant(false);
01481 }
01482 
01483 /// FoldICmpCstShlCst - Handle "(icmp eq/ne (shl const2, A), const1)" ->
01484 /// (icmp eq/ne A, TrailingZeros(const1) - TrailingZeros(const2)).
01485 Instruction *InstCombiner::FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
01486                                              ConstantInt *CI1,
01487                                              ConstantInt *CI2) {
01488   assert(I.isEquality() && "Cannot fold icmp gt/lt");
01489 
01490   auto getConstant = [&I, this](bool IsTrue) {
01491     if (I.getPredicate() == I.ICMP_NE)
01492       IsTrue = !IsTrue;
01493     return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), IsTrue));
01494   };
01495 
01496   auto getICmp = [&I](CmpInst::Predicate Pred, Value *LHS, Value *RHS) {
01497     if (I.getPredicate() == I.ICMP_NE)
01498       Pred = CmpInst::getInversePredicate(Pred);
01499     return new ICmpInst(Pred, LHS, RHS);
01500   };
01501 
01502   APInt AP1 = CI1->getValue();
01503   APInt AP2 = CI2->getValue();
01504 
01505   // Don't bother doing any work for cases which InstSimplify handles.
01506   if (AP2 == 0)
01507     return nullptr;
01508 
01509   unsigned AP2TrailingZeros = AP2.countTrailingZeros();
01510 
01511   if (!AP1 && AP2TrailingZeros != 0)
01512     return getICmp(I.ICMP_UGE, A,
01513                    ConstantInt::get(A->getType(), AP2.getBitWidth() - AP2TrailingZeros));
01514 
01515   if (AP1 == AP2)
01516     return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
01517 
01518   // Get the distance between the lowest bits that are set.
01519   int Shift = AP1.countTrailingZeros() - AP2TrailingZeros;
01520 
01521   if (Shift > 0 && AP2.shl(Shift) == AP1)
01522     return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
01523 
01524   // Shifting const2 will never be equal to const1.
01525   return getConstant(false);
01526 }
01527 
01528 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
01529 ///
01530 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
01531                                                           Instruction *LHSI,
01532                                                           ConstantInt *RHS) {
01533   const APInt &RHSV = RHS->getValue();
01534 
01535   switch (LHSI->getOpcode()) {
01536   case Instruction::Trunc:
01537     if (RHS->isOne() && RHSV.getBitWidth() > 1) {
01538       // icmp slt trunc(signum(V)) 1 --> icmp slt V, 1
01539       Value *V = nullptr;
01540       if (ICI.getPredicate() == ICmpInst::ICMP_SLT &&
01541           match(LHSI->getOperand(0), m_Signum(m_Value(V))))
01542         return new ICmpInst(ICmpInst::ICMP_SLT, V,
01543                             ConstantInt::get(V->getType(), 1));
01544     }
01545     if (ICI.isEquality() && LHSI->hasOneUse()) {
01546       // Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all
01547       // of the high bits truncated out of x are known.
01548       unsigned DstBits = LHSI->getType()->getPrimitiveSizeInBits(),
01549              SrcBits = LHSI->getOperand(0)->getType()->getPrimitiveSizeInBits();
01550       APInt KnownZero(SrcBits, 0), KnownOne(SrcBits, 0);
01551       computeKnownBits(LHSI->getOperand(0), KnownZero, KnownOne, 0, &ICI);
01552 
01553       // If all the high bits are known, we can do this xform.
01554       if ((KnownZero|KnownOne).countLeadingOnes() >= SrcBits-DstBits) {
01555         // Pull in the high bits from known-ones set.
01556         APInt NewRHS = RHS->getValue().zext(SrcBits);
01557         NewRHS |= KnownOne & APInt::getHighBitsSet(SrcBits, SrcBits-DstBits);
01558         return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
01559                             Builder->getInt(NewRHS));
01560       }
01561     }
01562     break;
01563 
01564   case Instruction::Xor:         // (icmp pred (xor X, XorCst), CI)
01565     if (ConstantInt *XorCst = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
01566       // If this is a comparison that tests the signbit (X < 0) or (x > -1),
01567       // fold the xor.
01568       if ((ICI.getPredicate() == ICmpInst::ICMP_SLT && RHSV == 0) ||
01569           (ICI.getPredicate() == ICmpInst::ICMP_SGT && RHSV.isAllOnesValue())) {
01570         Value *CompareVal = LHSI->getOperand(0);
01571 
01572         // If the sign bit of the XorCst is not set, there is no change to
01573         // the operation, just stop using the Xor.
01574         if (!XorCst->isNegative()) {
01575           ICI.setOperand(0, CompareVal);
01576           Worklist.Add(LHSI);
01577           return &ICI;
01578         }
01579 
01580         // Was the old condition true if the operand is positive?
01581         bool isTrueIfPositive = ICI.getPredicate() == ICmpInst::ICMP_SGT;
01582 
01583         // If so, the new one isn't.
01584         isTrueIfPositive ^= true;
01585 
01586         if (isTrueIfPositive)
01587           return new ICmpInst(ICmpInst::ICMP_SGT, CompareVal,
01588                               SubOne(RHS));
01589         else
01590           return new ICmpInst(ICmpInst::ICMP_SLT, CompareVal,
01591                               AddOne(RHS));
01592       }
01593 
01594       if (LHSI->hasOneUse()) {
01595         // (icmp u/s (xor A SignBit), C) -> (icmp s/u A, (xor C SignBit))
01596         if (!ICI.isEquality() && XorCst->getValue().isSignBit()) {
01597           const APInt &SignBit = XorCst->getValue();
01598           ICmpInst::Predicate Pred = ICI.isSigned()
01599                                          ? ICI.getUnsignedPredicate()
01600                                          : ICI.getSignedPredicate();
01601           return new ICmpInst(Pred, LHSI->getOperand(0),
01602                               Builder->getInt(RHSV ^ SignBit));
01603         }
01604 
01605         // (icmp u/s (xor A ~SignBit), C) -> (icmp s/u (xor C ~SignBit), A)
01606         if (!ICI.isEquality() && XorCst->isMaxValue(true)) {
01607           const APInt &NotSignBit = XorCst->getValue();
01608           ICmpInst::Predicate Pred = ICI.isSigned()
01609                                          ? ICI.getUnsignedPredicate()
01610                                          : ICI.getSignedPredicate();
01611           Pred = ICI.getSwappedPredicate(Pred);
01612           return new ICmpInst(Pred, LHSI->getOperand(0),
01613                               Builder->getInt(RHSV ^ NotSignBit));
01614         }
01615       }
01616 
01617       // (icmp ugt (xor X, C), ~C) -> (icmp ult X, C)
01618       //   iff -C is a power of 2
01619       if (ICI.getPredicate() == ICmpInst::ICMP_UGT &&
01620           XorCst->getValue() == ~RHSV && (RHSV + 1).isPowerOf2())
01621         return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0), XorCst);
01622 
01623       // (icmp ult (xor X, C), -C) -> (icmp uge X, C)
01624       //   iff -C is a power of 2
01625       if (ICI.getPredicate() == ICmpInst::ICMP_ULT &&
01626           XorCst->getValue() == -RHSV && RHSV.isPowerOf2())
01627         return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0), XorCst);
01628     }
01629     break;
01630   case Instruction::And:         // (icmp pred (and X, AndCst), RHS)
01631     if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
01632         LHSI->getOperand(0)->hasOneUse()) {
01633       ConstantInt *AndCst = cast<ConstantInt>(LHSI->getOperand(1));
01634 
01635       // If the LHS is an AND of a truncating cast, we can widen the
01636       // and/compare to be the input width without changing the value
01637       // produced, eliminating a cast.
01638       if (TruncInst *Cast = dyn_cast<TruncInst>(LHSI->getOperand(0))) {
01639         // We can do this transformation if either the AND constant does not
01640         // have its sign bit set or if it is an equality comparison.
01641         // Extending a relational comparison when we're checking the sign
01642         // bit would not work.
01643         if (ICI.isEquality() ||
01644             (!AndCst->isNegative() && RHSV.isNonNegative())) {
01645           Value *NewAnd =
01646             Builder->CreateAnd(Cast->getOperand(0),
01647                                ConstantExpr::getZExt(AndCst, Cast->getSrcTy()));
01648           NewAnd->takeName(LHSI);
01649           return new ICmpInst(ICI.getPredicate(), NewAnd,
01650                               ConstantExpr::getZExt(RHS, Cast->getSrcTy()));
01651         }
01652       }
01653 
01654       // If the LHS is an AND of a zext, and we have an equality compare, we can
01655       // shrink the and/compare to the smaller type, eliminating the cast.
01656       if (ZExtInst *Cast = dyn_cast<ZExtInst>(LHSI->getOperand(0))) {
01657         IntegerType *Ty = cast<IntegerType>(Cast->getSrcTy());
01658         // Make sure we don't compare the upper bits, SimplifyDemandedBits
01659         // should fold the icmp to true/false in that case.
01660         if (ICI.isEquality() && RHSV.getActiveBits() <= Ty->getBitWidth()) {
01661           Value *NewAnd =
01662             Builder->CreateAnd(Cast->getOperand(0),
01663                                ConstantExpr::getTrunc(AndCst, Ty));
01664           NewAnd->takeName(LHSI);
01665           return new ICmpInst(ICI.getPredicate(), NewAnd,
01666                               ConstantExpr::getTrunc(RHS, Ty));
01667         }
01668       }
01669 
01670       // If this is: (X >> C1) & C2 != C3 (where any shift and any compare
01671       // could exist), turn it into (X & (C2 << C1)) != (C3 << C1).  This
01672       // happens a LOT in code produced by the C front-end, for bitfield
01673       // access.
01674       BinaryOperator *Shift = dyn_cast<BinaryOperator>(LHSI->getOperand(0));
01675       if (Shift && !Shift->isShift())
01676         Shift = nullptr;
01677 
01678       ConstantInt *ShAmt;
01679       ShAmt = Shift ? dyn_cast<ConstantInt>(Shift->getOperand(1)) : nullptr;
01680 
01681       // This seemingly simple opportunity to fold away a shift turns out to
01682       // be rather complicated. See PR17827
01683       // ( http://llvm.org/bugs/show_bug.cgi?id=17827 ) for details.
01684       if (ShAmt) {
01685         bool CanFold = false;
01686         unsigned ShiftOpcode = Shift->getOpcode();
01687         if (ShiftOpcode == Instruction::AShr) {
01688           // There may be some constraints that make this possible,
01689           // but nothing simple has been discovered yet.
01690           CanFold = false;
01691         } else if (ShiftOpcode == Instruction::Shl) {
01692           // For a left shift, we can fold if the comparison is not signed.
01693           // We can also fold a signed comparison if the mask value and
01694           // comparison value are not negative. These constraints may not be
01695           // obvious, but we can prove that they are correct using an SMT
01696           // solver.
01697           if (!ICI.isSigned() || (!AndCst->isNegative() && !RHS->isNegative()))
01698             CanFold = true;
01699         } else if (ShiftOpcode == Instruction::LShr) {
01700           // For a logical right shift, we can fold if the comparison is not
01701           // signed. We can also fold a signed comparison if the shifted mask
01702           // value and the shifted comparison value are not negative.
01703           // These constraints may not be obvious, but we can prove that they
01704           // are correct using an SMT solver.
01705           if (!ICI.isSigned())
01706             CanFold = true;
01707           else {
01708             ConstantInt *ShiftedAndCst =
01709               cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt));
01710             ConstantInt *ShiftedRHSCst =
01711               cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt));
01712             
01713             if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative())
01714               CanFold = true;
01715           }
01716         }
01717 
01718         if (CanFold) {
01719           Constant *NewCst;
01720           if (ShiftOpcode == Instruction::Shl)
01721             NewCst = ConstantExpr::getLShr(RHS, ShAmt);
01722           else
01723             NewCst = ConstantExpr::getShl(RHS, ShAmt);
01724 
01725           // Check to see if we are shifting out any of the bits being
01726           // compared.
01727           if (ConstantExpr::get(ShiftOpcode, NewCst, ShAmt) != RHS) {
01728             // If we shifted bits out, the fold is not going to work out.
01729             // As a special case, check to see if this means that the
01730             // result is always true or false now.
01731             if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
01732               return ReplaceInstUsesWith(ICI, Builder->getFalse());
01733             if (ICI.getPredicate() == ICmpInst::ICMP_NE)
01734               return ReplaceInstUsesWith(ICI, Builder->getTrue());
01735           } else {
01736             ICI.setOperand(1, NewCst);
01737             Constant *NewAndCst;
01738             if (ShiftOpcode == Instruction::Shl)
01739               NewAndCst = ConstantExpr::getLShr(AndCst, ShAmt);
01740             else
01741               NewAndCst = ConstantExpr::getShl(AndCst, ShAmt);
01742             LHSI->setOperand(1, NewAndCst);
01743             LHSI->setOperand(0, Shift->getOperand(0));
01744             Worklist.Add(Shift); // Shift is dead.
01745             return &ICI;
01746           }
01747         }
01748       }
01749 
01750       // Turn ((X >> Y) & C) == 0  into  (X & (C << Y)) == 0.  The later is
01751       // preferable because it allows the C<<Y expression to be hoisted out
01752       // of a loop if Y is invariant and X is not.
01753       if (Shift && Shift->hasOneUse() && RHSV == 0 &&
01754           ICI.isEquality() && !Shift->isArithmeticShift() &&
01755           !isa<Constant>(Shift->getOperand(0))) {
01756         // Compute C << Y.
01757         Value *NS;
01758         if (Shift->getOpcode() == Instruction::LShr) {
01759           NS = Builder->CreateShl(AndCst, Shift->getOperand(1));
01760         } else {
01761           // Insert a logical shift.
01762           NS = Builder->CreateLShr(AndCst, Shift->getOperand(1));
01763         }
01764 
01765         // Compute X & (C << Y).
01766         Value *NewAnd =
01767           Builder->CreateAnd(Shift->getOperand(0), NS, LHSI->getName());
01768 
01769         ICI.setOperand(0, NewAnd);
01770         return &ICI;
01771       }
01772 
01773       // (icmp pred (and (or (lshr X, Y), X), 1), 0) -->
01774       //    (icmp pred (and X, (or (shl 1, Y), 1), 0))
01775       //
01776       // iff pred isn't signed
01777       {
01778         Value *X, *Y, *LShr;
01779         if (!ICI.isSigned() && RHSV == 0) {
01780           if (match(LHSI->getOperand(1), m_One())) {
01781             Constant *One = cast<Constant>(LHSI->getOperand(1));
01782             Value *Or = LHSI->getOperand(0);
01783             if (match(Or, m_Or(m_Value(LShr), m_Value(X))) &&
01784                 match(LShr, m_LShr(m_Specific(X), m_Value(Y)))) {
01785               unsigned UsesRemoved = 0;
01786               if (LHSI->hasOneUse())
01787                 ++UsesRemoved;
01788               if (Or->hasOneUse())
01789                 ++UsesRemoved;
01790               if (LShr->hasOneUse())
01791                 ++UsesRemoved;
01792               Value *NewOr = nullptr;
01793               // Compute X & ((1 << Y) | 1)
01794               if (auto *C = dyn_cast<Constant>(Y)) {
01795                 if (UsesRemoved >= 1)
01796                   NewOr =
01797                       ConstantExpr::getOr(ConstantExpr::getNUWShl(One, C), One);
01798               } else {
01799                 if (UsesRemoved >= 3)
01800                   NewOr = Builder->CreateOr(Builder->CreateShl(One, Y,
01801                                                                LShr->getName(),
01802                                                                /*HasNUW=*/true),
01803                                             One, Or->getName());
01804               }
01805               if (NewOr) {
01806                 Value *NewAnd = Builder->CreateAnd(X, NewOr, LHSI->getName());
01807                 ICI.setOperand(0, NewAnd);
01808                 return &ICI;
01809               }
01810             }
01811           }
01812         }
01813       }
01814 
01815       // Replace ((X & AndCst) > RHSV) with ((X & AndCst) != 0), if any
01816       // bit set in (X & AndCst) will produce a result greater than RHSV.
01817       if (ICI.getPredicate() == ICmpInst::ICMP_UGT) {
01818         unsigned NTZ = AndCst->getValue().countTrailingZeros();
01819         if ((NTZ < AndCst->getBitWidth()) &&
01820             APInt::getOneBitSet(AndCst->getBitWidth(), NTZ).ugt(RHSV))
01821           return new ICmpInst(ICmpInst::ICMP_NE, LHSI,
01822                               Constant::getNullValue(RHS->getType()));
01823       }
01824     }
01825 
01826     // Try to optimize things like "A[i]&42 == 0" to index computations.
01827     if (LoadInst *LI = dyn_cast<LoadInst>(LHSI->getOperand(0))) {
01828       if (GetElementPtrInst *GEP =
01829           dyn_cast<GetElementPtrInst>(LI->getOperand(0)))
01830         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
01831           if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
01832               !LI->isVolatile() && isa<ConstantInt>(LHSI->getOperand(1))) {
01833             ConstantInt *C = cast<ConstantInt>(LHSI->getOperand(1));
01834             if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV,ICI, C))
01835               return Res;
01836           }
01837     }
01838 
01839     // X & -C == -C -> X >  u ~C
01840     // X & -C != -C -> X <= u ~C
01841     //   iff C is a power of 2
01842     if (ICI.isEquality() && RHS == LHSI->getOperand(1) && (-RHSV).isPowerOf2())
01843       return new ICmpInst(
01844           ICI.getPredicate() == ICmpInst::ICMP_EQ ? ICmpInst::ICMP_UGT
01845                                                   : ICmpInst::ICMP_ULE,
01846           LHSI->getOperand(0), SubOne(RHS));
01847 
01848     // (icmp eq (and %A, C), 0) -> (icmp sgt (trunc %A), -1)
01849     //   iff C is a power of 2
01850     if (ICI.isEquality() && LHSI->hasOneUse() && match(RHS, m_Zero())) {
01851       if (auto *CI = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
01852         const APInt &AI = CI->getValue();
01853         int32_t ExactLogBase2 = AI.exactLogBase2();
01854         if (ExactLogBase2 != -1 && DL.isLegalInteger(ExactLogBase2 + 1)) {
01855           Type *NTy = IntegerType::get(ICI.getContext(), ExactLogBase2 + 1);
01856           Value *Trunc = Builder->CreateTrunc(LHSI->getOperand(0), NTy);
01857           return new ICmpInst(ICI.getPredicate() == ICmpInst::ICMP_EQ
01858                                   ? ICmpInst::ICMP_SGE
01859                                   : ICmpInst::ICMP_SLT,
01860                               Trunc, Constant::getNullValue(NTy));
01861         }
01862       }
01863     }
01864     break;
01865 
01866   case Instruction::Or: {
01867     if (RHS->isOne()) {
01868       // icmp slt signum(V) 1 --> icmp slt V, 1
01869       Value *V = nullptr;
01870       if (ICI.getPredicate() == ICmpInst::ICMP_SLT &&
01871           match(LHSI, m_Signum(m_Value(V))))
01872         return new ICmpInst(ICmpInst::ICMP_SLT, V,
01873                             ConstantInt::get(V->getType(), 1));
01874     }
01875 
01876     if (!ICI.isEquality() || !RHS->isNullValue() || !LHSI->hasOneUse())
01877       break;
01878     Value *P, *Q;
01879     if (match(LHSI, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) {
01880       // Simplify icmp eq (or (ptrtoint P), (ptrtoint Q)), 0
01881       // -> and (icmp eq P, null), (icmp eq Q, null).
01882       Value *ICIP = Builder->CreateICmp(ICI.getPredicate(), P,
01883                                         Constant::getNullValue(P->getType()));
01884       Value *ICIQ = Builder->CreateICmp(ICI.getPredicate(), Q,
01885                                         Constant::getNullValue(Q->getType()));
01886       Instruction *Op;
01887       if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
01888         Op = BinaryOperator::CreateAnd(ICIP, ICIQ);
01889       else
01890         Op = BinaryOperator::CreateOr(ICIP, ICIQ);
01891       return Op;
01892     }
01893     break;
01894   }
01895 
01896   case Instruction::Mul: {       // (icmp pred (mul X, Val), CI)
01897     ConstantInt *Val = dyn_cast<ConstantInt>(LHSI->getOperand(1));
01898     if (!Val) break;
01899 
01900     // If this is a signed comparison to 0 and the mul is sign preserving,
01901     // use the mul LHS operand instead.
01902     ICmpInst::Predicate pred = ICI.getPredicate();
01903     if (isSignTest(pred, RHS) && !Val->isZero() &&
01904         cast<BinaryOperator>(LHSI)->hasNoSignedWrap())
01905       return new ICmpInst(Val->isNegative() ?
01906                           ICmpInst::getSwappedPredicate(pred) : pred,
01907                           LHSI->getOperand(0),
01908                           Constant::getNullValue(RHS->getType()));
01909 
01910     break;
01911   }
01912 
01913   case Instruction::Shl: {       // (icmp pred (shl X, ShAmt), CI)
01914     uint32_t TypeBits = RHSV.getBitWidth();
01915     ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
01916     if (!ShAmt) {
01917       Value *X;
01918       // (1 << X) pred P2 -> X pred Log2(P2)
01919       if (match(LHSI, m_Shl(m_One(), m_Value(X)))) {
01920         bool RHSVIsPowerOf2 = RHSV.isPowerOf2();
01921         ICmpInst::Predicate Pred = ICI.getPredicate();
01922         if (ICI.isUnsigned()) {
01923           if (!RHSVIsPowerOf2) {
01924             // (1 << X) <  30 -> X <= 4
01925             // (1 << X) <= 30 -> X <= 4
01926             // (1 << X) >= 30 -> X >  4
01927             // (1 << X) >  30 -> X >  4
01928             if (Pred == ICmpInst::ICMP_ULT)
01929               Pred = ICmpInst::ICMP_ULE;
01930             else if (Pred == ICmpInst::ICMP_UGE)
01931               Pred = ICmpInst::ICMP_UGT;
01932           }
01933           unsigned RHSLog2 = RHSV.logBase2();
01934 
01935           // (1 << X) >= 2147483648 -> X >= 31 -> X == 31
01936           // (1 << X) <  2147483648 -> X <  31 -> X != 31
01937           if (RHSLog2 == TypeBits-1) {
01938             if (Pred == ICmpInst::ICMP_UGE)
01939               Pred = ICmpInst::ICMP_EQ;
01940             else if (Pred == ICmpInst::ICMP_ULT)
01941               Pred = ICmpInst::ICMP_NE;
01942           }
01943 
01944           return new ICmpInst(Pred, X,
01945                               ConstantInt::get(RHS->getType(), RHSLog2));
01946         } else if (ICI.isSigned()) {
01947           if (RHSV.isAllOnesValue()) {
01948             // (1 << X) <= -1 -> X == 31
01949             if (Pred == ICmpInst::ICMP_SLE)
01950               return new ICmpInst(ICmpInst::ICMP_EQ, X,
01951                                   ConstantInt::get(RHS->getType(), TypeBits-1));
01952 
01953             // (1 << X) >  -1 -> X != 31
01954             if (Pred == ICmpInst::ICMP_SGT)
01955               return new ICmpInst(ICmpInst::ICMP_NE, X,
01956                                   ConstantInt::get(RHS->getType(), TypeBits-1));
01957           } else if (!RHSV) {
01958             // (1 << X) <  0 -> X == 31
01959             // (1 << X) <= 0 -> X == 31
01960             if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
01961               return new ICmpInst(ICmpInst::ICMP_EQ, X,
01962                                   ConstantInt::get(RHS->getType(), TypeBits-1));
01963 
01964             // (1 << X) >= 0 -> X != 31
01965             // (1 << X) >  0 -> X != 31
01966             if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE)
01967               return new ICmpInst(ICmpInst::ICMP_NE, X,
01968                                   ConstantInt::get(RHS->getType(), TypeBits-1));
01969           }
01970         } else if (ICI.isEquality()) {
01971           if (RHSVIsPowerOf2)
01972             return new ICmpInst(
01973                 Pred, X, ConstantInt::get(RHS->getType(), RHSV.logBase2()));
01974         }
01975       }
01976       break;
01977     }
01978 
01979     // Check that the shift amount is in range.  If not, don't perform
01980     // undefined shifts.  When the shift is visited it will be
01981     // simplified.
01982     if (ShAmt->uge(TypeBits))
01983       break;
01984 
01985     if (ICI.isEquality()) {
01986       // If we are comparing against bits always shifted out, the
01987       // comparison cannot succeed.
01988       Constant *Comp =
01989         ConstantExpr::getShl(ConstantExpr::getLShr(RHS, ShAmt),
01990                                                                  ShAmt);
01991       if (Comp != RHS) {// Comparing against a bit that we know is zero.
01992         bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
01993         Constant *Cst = Builder->getInt1(IsICMP_NE);
01994         return ReplaceInstUsesWith(ICI, Cst);
01995       }
01996 
01997       // If the shift is NUW, then it is just shifting out zeros, no need for an
01998       // AND.
01999       if (cast<BinaryOperator>(LHSI)->hasNoUnsignedWrap())
02000         return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
02001                             ConstantExpr::getLShr(RHS, ShAmt));
02002 
02003       // If the shift is NSW and we compare to 0, then it is just shifting out
02004       // sign bits, no need for an AND either.
02005       if (cast<BinaryOperator>(LHSI)->hasNoSignedWrap() && RHSV == 0)
02006         return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
02007                             ConstantExpr::getLShr(RHS, ShAmt));
02008 
02009       if (LHSI->hasOneUse()) {
02010         // Otherwise strength reduce the shift into an and.
02011         uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
02012         Constant *Mask = Builder->getInt(APInt::getLowBitsSet(TypeBits,
02013                                                           TypeBits - ShAmtVal));
02014 
02015         Value *And =
02016           Builder->CreateAnd(LHSI->getOperand(0),Mask, LHSI->getName()+".mask");
02017         return new ICmpInst(ICI.getPredicate(), And,
02018                             ConstantExpr::getLShr(RHS, ShAmt));
02019       }
02020     }
02021 
02022     // If this is a signed comparison to 0 and the shift is sign preserving,
02023     // use the shift LHS operand instead.
02024     ICmpInst::Predicate pred = ICI.getPredicate();
02025     if (isSignTest(pred, RHS) &&
02026         cast<BinaryOperator>(LHSI)->hasNoSignedWrap())
02027       return new ICmpInst(pred,
02028                           LHSI->getOperand(0),
02029                           Constant::getNullValue(RHS->getType()));
02030 
02031     // Otherwise, if this is a comparison of the sign bit, simplify to and/test.
02032     bool TrueIfSigned = false;
02033     if (LHSI->hasOneUse() &&
02034         isSignBitCheck(ICI.getPredicate(), RHS, TrueIfSigned)) {
02035       // (X << 31) <s 0  --> (X&1) != 0
02036       Constant *Mask = ConstantInt::get(LHSI->getOperand(0)->getType(),
02037                                         APInt::getOneBitSet(TypeBits,
02038                                             TypeBits-ShAmt->getZExtValue()-1));
02039       Value *And =
02040         Builder->CreateAnd(LHSI->getOperand(0), Mask, LHSI->getName()+".mask");
02041       return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ,
02042                           And, Constant::getNullValue(And->getType()));
02043     }
02044 
02045     // Transform (icmp pred iM (shl iM %v, N), CI)
02046     // -> (icmp pred i(M-N) (trunc %v iM to i(M-N)), (trunc (CI>>N))
02047     // Transform the shl to a trunc if (trunc (CI>>N)) has no loss and M-N.
02048     // This enables to get rid of the shift in favor of a trunc which can be
02049     // free on the target. It has the additional benefit of comparing to a
02050     // smaller constant, which will be target friendly.
02051     unsigned Amt = ShAmt->getLimitedValue(TypeBits-1);
02052     if (LHSI->hasOneUse() &&
02053         Amt != 0 && RHSV.countTrailingZeros() >= Amt) {
02054       Type *NTy = IntegerType::get(ICI.getContext(), TypeBits - Amt);
02055       Constant *NCI = ConstantExpr::getTrunc(
02056                         ConstantExpr::getAShr(RHS,
02057                           ConstantInt::get(RHS->getType(), Amt)),
02058                         NTy);
02059       return new ICmpInst(ICI.getPredicate(),
02060                           Builder->CreateTrunc(LHSI->getOperand(0), NTy),
02061                           NCI);
02062     }
02063 
02064     break;
02065   }
02066 
02067   case Instruction::LShr:         // (icmp pred (shr X, ShAmt), CI)
02068   case Instruction::AShr: {
02069     // Handle equality comparisons of shift-by-constant.
02070     BinaryOperator *BO = cast<BinaryOperator>(LHSI);
02071     if (ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
02072       if (Instruction *Res = FoldICmpShrCst(ICI, BO, ShAmt))
02073         return Res;
02074     }
02075 
02076     // Handle exact shr's.
02077     if (ICI.isEquality() && BO->isExact() && BO->hasOneUse()) {
02078       if (RHSV.isMinValue())
02079         return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), RHS);
02080     }
02081     break;
02082   }
02083 
02084   case Instruction::SDiv:
02085   case Instruction::UDiv:
02086     // Fold: icmp pred ([us]div X, C1), C2 -> range test
02087     // Fold this div into the comparison, producing a range check.
02088     // Determine, based on the divide type, what the range is being
02089     // checked.  If there is an overflow on the low or high side, remember
02090     // it, otherwise compute the range [low, hi) bounding the new value.
02091     // See: InsertRangeTest above for the kinds of replacements possible.
02092     if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1)))
02093       if (Instruction *R = FoldICmpDivCst(ICI, cast<BinaryOperator>(LHSI),
02094                                           DivRHS))
02095         return R;
02096     break;
02097 
02098   case Instruction::Sub: {
02099     ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(0));
02100     if (!LHSC) break;
02101     const APInt &LHSV = LHSC->getValue();
02102 
02103     // C1-X <u C2 -> (X|(C2-1)) == C1
02104     //   iff C1 & (C2-1) == C2-1
02105     //       C2 is a power of 2
02106     if (ICI.getPredicate() == ICmpInst::ICMP_ULT && LHSI->hasOneUse() &&
02107         RHSV.isPowerOf2() && (LHSV & (RHSV - 1)) == (RHSV - 1))
02108       return new ICmpInst(ICmpInst::ICMP_EQ,
02109                           Builder->CreateOr(LHSI->getOperand(1), RHSV - 1),
02110                           LHSC);
02111 
02112     // C1-X >u C2 -> (X|C2) != C1
02113     //   iff C1 & C2 == C2
02114     //       C2+1 is a power of 2
02115     if (ICI.getPredicate() == ICmpInst::ICMP_UGT && LHSI->hasOneUse() &&
02116         (RHSV + 1).isPowerOf2() && (LHSV & RHSV) == RHSV)
02117       return new ICmpInst(ICmpInst::ICMP_NE,
02118                           Builder->CreateOr(LHSI->getOperand(1), RHSV), LHSC);
02119     break;
02120   }
02121 
02122   case Instruction::Add:
02123     // Fold: icmp pred (add X, C1), C2
02124     if (!ICI.isEquality()) {
02125       ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(1));
02126       if (!LHSC) break;
02127       const APInt &LHSV = LHSC->getValue();
02128 
02129       ConstantRange CR = ICI.makeConstantRange(ICI.getPredicate(), RHSV)
02130                             .subtract(LHSV);
02131 
02132       if (ICI.isSigned()) {
02133         if (CR.getLower().isSignBit()) {
02134           return new ICmpInst(ICmpInst::ICMP_SLT, LHSI->getOperand(0),
02135                               Builder->getInt(CR.getUpper()));
02136         } else if (CR.getUpper().isSignBit()) {
02137           return new ICmpInst(ICmpInst::ICMP_SGE, LHSI->getOperand(0),
02138                               Builder->getInt(CR.getLower()));
02139         }
02140       } else {
02141         if (CR.getLower().isMinValue()) {
02142           return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0),
02143                               Builder->getInt(CR.getUpper()));
02144         } else if (CR.getUpper().isMinValue()) {
02145           return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0),
02146                               Builder->getInt(CR.getLower()));
02147         }
02148       }
02149 
02150       // X-C1 <u C2 -> (X & -C2) == C1
02151       //   iff C1 & (C2-1) == 0
02152       //       C2 is a power of 2
02153       if (ICI.getPredicate() == ICmpInst::ICMP_ULT && LHSI->hasOneUse() &&
02154           RHSV.isPowerOf2() && (LHSV & (RHSV - 1)) == 0)
02155         return new ICmpInst(ICmpInst::ICMP_EQ,
02156                             Builder->CreateAnd(LHSI->getOperand(0), -RHSV),
02157                             ConstantExpr::getNeg(LHSC));
02158 
02159       // X-C1 >u C2 -> (X & ~C2) != C1
02160       //   iff C1 & C2 == 0
02161       //       C2+1 is a power of 2
02162       if (ICI.getPredicate() == ICmpInst::ICMP_UGT && LHSI->hasOneUse() &&
02163           (RHSV + 1).isPowerOf2() && (LHSV & RHSV) == 0)
02164         return new ICmpInst(ICmpInst::ICMP_NE,
02165                             Builder->CreateAnd(LHSI->getOperand(0), ~RHSV),
02166                             ConstantExpr::getNeg(LHSC));
02167     }
02168     break;
02169   }
02170 
02171   // Simplify icmp_eq and icmp_ne instructions with integer constant RHS.
02172   if (ICI.isEquality()) {
02173     bool isICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
02174 
02175     // If the first operand is (add|sub|and|or|xor|rem) with a constant, and
02176     // the second operand is a constant, simplify a bit.
02177     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(LHSI)) {
02178       switch (BO->getOpcode()) {
02179       case Instruction::SRem:
02180         // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
02181         if (RHSV == 0 && isa<ConstantInt>(BO->getOperand(1)) &&BO->hasOneUse()){
02182           const APInt &V = cast<ConstantInt>(BO->getOperand(1))->getValue();
02183           if (V.sgt(1) && V.isPowerOf2()) {
02184             Value *NewRem =
02185               Builder->CreateURem(BO->getOperand(0), BO->getOperand(1),
02186                                   BO->getName());
02187             return new ICmpInst(ICI.getPredicate(), NewRem,
02188                                 Constant::getNullValue(BO->getType()));
02189           }
02190         }
02191         break;
02192       case Instruction::Add:
02193         // Replace ((add A, B) != C) with (A != C-B) if B & C are constants.
02194         if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
02195           if (BO->hasOneUse())
02196             return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
02197                                 ConstantExpr::getSub(RHS, BOp1C));
02198         } else if (RHSV == 0) {
02199           // Replace ((add A, B) != 0) with (A != -B) if A or B is
02200           // efficiently invertible, or if the add has just this one use.
02201           Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
02202 
02203           if (Value *NegVal = dyn_castNegVal(BOp1))
02204             return new ICmpInst(ICI.getPredicate(), BOp0, NegVal);
02205           if (Value *NegVal = dyn_castNegVal(BOp0))
02206             return new ICmpInst(ICI.getPredicate(), NegVal, BOp1);
02207           if (BO->hasOneUse()) {
02208             Value *Neg = Builder->CreateNeg(BOp1);
02209             Neg->takeName(BO);
02210             return new ICmpInst(ICI.getPredicate(), BOp0, Neg);
02211           }
02212         }
02213         break;
02214       case Instruction::Xor:
02215         // For the xor case, we can xor two constants together, eliminating
02216         // the explicit xor.
02217         if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
02218           return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
02219                               ConstantExpr::getXor(RHS, BOC));
02220         } else if (RHSV == 0) {
02221           // Replace ((xor A, B) != 0) with (A != B)
02222           return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
02223                               BO->getOperand(1));
02224         }
02225         break;
02226       case Instruction::Sub:
02227         // Replace ((sub A, B) != C) with (B != A-C) if A & C are constants.
02228         if (ConstantInt *BOp0C = dyn_cast<ConstantInt>(BO->getOperand(0))) {
02229           if (BO->hasOneUse())
02230             return new ICmpInst(ICI.getPredicate(), BO->getOperand(1),
02231                                 ConstantExpr::getSub(BOp0C, RHS));
02232         } else if (RHSV == 0) {
02233           // Replace ((sub A, B) != 0) with (A != B)
02234           return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
02235                               BO->getOperand(1));
02236         }
02237         break;
02238       case Instruction::Or:
02239         // If bits are being or'd in that are not present in the constant we
02240         // are comparing against, then the comparison could never succeed!
02241         if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
02242           Constant *NotCI = ConstantExpr::getNot(RHS);
02243           if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
02244             return ReplaceInstUsesWith(ICI, Builder->getInt1(isICMP_NE));
02245         }
02246         break;
02247 
02248       case Instruction::And:
02249         if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
02250           // If bits are being compared against that are and'd out, then the
02251           // comparison can never succeed!
02252           if ((RHSV & ~BOC->getValue()) != 0)
02253             return ReplaceInstUsesWith(ICI, Builder->getInt1(isICMP_NE));
02254 
02255           // If we have ((X & C) == C), turn it into ((X & C) != 0).
02256           if (RHS == BOC && RHSV.isPowerOf2())
02257             return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ :
02258                                 ICmpInst::ICMP_NE, LHSI,
02259                                 Constant::getNullValue(RHS->getType()));
02260 
02261           // Don't perform the following transforms if the AND has multiple uses
02262           if (!BO->hasOneUse())
02263             break;
02264 
02265           // Replace (and X, (1 << size(X)-1) != 0) with x s< 0
02266           if (BOC->getValue().isSignBit()) {
02267             Value *X = BO->getOperand(0);
02268             Constant *Zero = Constant::getNullValue(X->getType());
02269             ICmpInst::Predicate pred = isICMP_NE ?
02270               ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
02271             return new ICmpInst(pred, X, Zero);
02272           }
02273 
02274           // ((X & ~7) == 0) --> X < 8
02275           if (RHSV == 0 && isHighOnes(BOC)) {
02276             Value *X = BO->getOperand(0);
02277             Constant *NegX = ConstantExpr::getNeg(BOC);
02278             ICmpInst::Predicate pred = isICMP_NE ?
02279               ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
02280             return new ICmpInst(pred, X, NegX);
02281           }
02282         }
02283         break;
02284       case Instruction::Mul:
02285         if (RHSV == 0 && BO->hasNoSignedWrap()) {
02286           if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
02287             // The trivial case (mul X, 0) is handled by InstSimplify
02288             // General case : (mul X, C) != 0 iff X != 0
02289             //                (mul X, C) == 0 iff X == 0
02290             if (!BOC->isZero())
02291               return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
02292                                   Constant::getNullValue(RHS->getType()));
02293           }
02294         }
02295         break;
02296       default: break;
02297       }
02298     } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(LHSI)) {
02299       // Handle icmp {eq|ne} <intrinsic>, intcst.
02300       switch (II->getIntrinsicID()) {
02301       case Intrinsic::bswap:
02302         Worklist.Add(II);
02303         ICI.setOperand(0, II->getArgOperand(0));
02304         ICI.setOperand(1, Builder->getInt(RHSV.byteSwap()));
02305         return &ICI;
02306       case Intrinsic::ctlz:
02307       case Intrinsic::cttz:
02308         // ctz(A) == bitwidth(a)  ->  A == 0 and likewise for !=
02309         if (RHSV == RHS->getType()->getBitWidth()) {
02310           Worklist.Add(II);
02311           ICI.setOperand(0, II->getArgOperand(0));
02312           ICI.setOperand(1, ConstantInt::get(RHS->getType(), 0));
02313           return &ICI;
02314         }
02315         break;
02316       case Intrinsic::ctpop:
02317         // popcount(A) == 0  ->  A == 0 and likewise for !=
02318         if (RHS->isZero()) {
02319           Worklist.Add(II);
02320           ICI.setOperand(0, II->getArgOperand(0));
02321           ICI.setOperand(1, RHS);
02322           return &ICI;
02323         }
02324         break;
02325       default:
02326         break;
02327       }
02328     }
02329   }
02330   return nullptr;
02331 }
02332 
02333 /// visitICmpInstWithCastAndCast - Handle icmp (cast x to y), (cast/cst).
02334 /// We only handle extending casts so far.
02335 ///
02336 Instruction *InstCombiner::visitICmpInstWithCastAndCast(ICmpInst &ICI) {
02337   const CastInst *LHSCI = cast<CastInst>(ICI.getOperand(0));
02338   Value *LHSCIOp        = LHSCI->getOperand(0);
02339   Type *SrcTy     = LHSCIOp->getType();
02340   Type *DestTy    = LHSCI->getType();
02341   Value *RHSCIOp;
02342 
02343   // Turn icmp (ptrtoint x), (ptrtoint/c) into a compare of the input if the
02344   // integer type is the same size as the pointer type.
02345   if (LHSCI->getOpcode() == Instruction::PtrToInt &&
02346       DL.getPointerTypeSizeInBits(SrcTy) == DestTy->getIntegerBitWidth()) {
02347     Value *RHSOp = nullptr;
02348     if (PtrToIntOperator *RHSC = dyn_cast<PtrToIntOperator>(ICI.getOperand(1))) {
02349       Value *RHSCIOp = RHSC->getOperand(0);
02350       if (RHSCIOp->getType()->getPointerAddressSpace() ==
02351           LHSCIOp->getType()->getPointerAddressSpace()) {
02352         RHSOp = RHSC->getOperand(0);
02353         // If the pointer types don't match, insert a bitcast.
02354         if (LHSCIOp->getType() != RHSOp->getType())
02355           RHSOp = Builder->CreateBitCast(RHSOp, LHSCIOp->getType());
02356       }
02357     } else if (Constant *RHSC = dyn_cast<Constant>(ICI.getOperand(1)))
02358       RHSOp = ConstantExpr::getIntToPtr(RHSC, SrcTy);
02359 
02360     if (RHSOp)
02361       return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSOp);
02362   }
02363 
02364   // The code below only handles extension cast instructions, so far.
02365   // Enforce this.
02366   if (LHSCI->getOpcode() != Instruction::ZExt &&
02367       LHSCI->getOpcode() != Instruction::SExt)
02368     return nullptr;
02369 
02370   bool isSignedExt = LHSCI->getOpcode() == Instruction::SExt;
02371   bool isSignedCmp = ICI.isSigned();
02372 
02373   if (CastInst *CI = dyn_cast<CastInst>(ICI.getOperand(1))) {
02374     // Not an extension from the same type?
02375     RHSCIOp = CI->getOperand(0);
02376     if (RHSCIOp->getType() != LHSCIOp->getType())
02377       return nullptr;
02378 
02379     // If the signedness of the two casts doesn't agree (i.e. one is a sext
02380     // and the other is a zext), then we can't handle this.
02381     if (CI->getOpcode() != LHSCI->getOpcode())
02382       return nullptr;
02383 
02384     // Deal with equality cases early.
02385     if (ICI.isEquality())
02386       return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
02387 
02388     // A signed comparison of sign extended values simplifies into a
02389     // signed comparison.
02390     if (isSignedCmp && isSignedExt)
02391       return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
02392 
02393     // The other three cases all fold into an unsigned comparison.
02394     return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, RHSCIOp);
02395   }
02396 
02397   // If we aren't dealing with a constant on the RHS, exit early
02398   ConstantInt *CI = dyn_cast<ConstantInt>(ICI.getOperand(1));
02399   if (!CI)
02400     return nullptr;
02401 
02402   // Compute the constant that would happen if we truncated to SrcTy then
02403   // reextended to DestTy.
02404   Constant *Res1 = ConstantExpr::getTrunc(CI, SrcTy);
02405   Constant *Res2 = ConstantExpr::getCast(LHSCI->getOpcode(),
02406                                                 Res1, DestTy);
02407 
02408   // If the re-extended constant didn't change...
02409   if (Res2 == CI) {
02410     // Deal with equality cases early.
02411     if (ICI.isEquality())
02412       return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
02413 
02414     // A signed comparison of sign extended values simplifies into a
02415     // signed comparison.
02416     if (isSignedExt && isSignedCmp)
02417       return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
02418 
02419     // The other three cases all fold into an unsigned comparison.
02420     return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, Res1);
02421   }
02422 
02423   // The re-extended constant changed so the constant cannot be represented
02424   // in the shorter type. Consequently, we cannot emit a simple comparison.
02425   // All the cases that fold to true or false will have already been handled
02426   // by SimplifyICmpInst, so only deal with the tricky case.
02427 
02428   if (isSignedCmp || !isSignedExt)
02429     return nullptr;
02430 
02431   // Evaluate the comparison for LT (we invert for GT below). LE and GE cases
02432   // should have been folded away previously and not enter in here.
02433 
02434   // We're performing an unsigned comp with a sign extended value.
02435   // This is true if the input is >= 0. [aka >s -1]
02436   Constant *NegOne = Constant::getAllOnesValue(SrcTy);
02437   Value *Result = Builder->CreateICmpSGT(LHSCIOp, NegOne, ICI.getName());
02438 
02439   // Finally, return the value computed.
02440   if (ICI.getPredicate() == ICmpInst::ICMP_ULT)
02441     return ReplaceInstUsesWith(ICI, Result);
02442 
02443   assert(ICI.getPredicate() == ICmpInst::ICMP_UGT && "ICmp should be folded!");
02444   return BinaryOperator::CreateNot(Result);
02445 }
02446 
02447 /// ProcessUGT_ADDCST_ADD - The caller has matched a pattern of the form:
02448 ///   I = icmp ugt (add (add A, B), CI2), CI1
02449 /// If this is of the form:
02450 ///   sum = a + b
02451 ///   if (sum+128 >u 255)
02452 /// Then replace it with llvm.sadd.with.overflow.i8.
02453 ///
02454 static Instruction *ProcessUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B,
02455                                           ConstantInt *CI2, ConstantInt *CI1,
02456                                           InstCombiner &IC) {
02457   // The transformation we're trying to do here is to transform this into an
02458   // llvm.sadd.with.overflow.  To do this, we have to replace the original add
02459   // with a narrower add, and discard the add-with-constant that is part of the
02460   // range check (if we can't eliminate it, this isn't profitable).
02461 
02462   // In order to eliminate the add-with-constant, the compare can be its only
02463   // use.
02464   Instruction *AddWithCst = cast<Instruction>(I.getOperand(0));
02465   if (!AddWithCst->hasOneUse()) return nullptr;
02466 
02467   // If CI2 is 2^7, 2^15, 2^31, then it might be an sadd.with.overflow.
02468   if (!CI2->getValue().isPowerOf2()) return nullptr;
02469   unsigned NewWidth = CI2->getValue().countTrailingZeros();
02470   if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31) return nullptr;
02471 
02472   // The width of the new add formed is 1 more than the bias.
02473   ++NewWidth;
02474 
02475   // Check to see that CI1 is an all-ones value with NewWidth bits.
02476   if (CI1->getBitWidth() == NewWidth ||
02477       CI1->getValue() != APInt::getLowBitsSet(CI1->getBitWidth(), NewWidth))
02478     return nullptr;
02479 
02480   // This is only really a signed overflow check if the inputs have been
02481   // sign-extended; check for that condition. For example, if CI2 is 2^31 and
02482   // the operands of the add are 64 bits wide, we need at least 33 sign bits.
02483   unsigned NeededSignBits = CI1->getBitWidth() - NewWidth + 1;
02484   if (IC.ComputeNumSignBits(A, 0, &I) < NeededSignBits ||
02485       IC.ComputeNumSignBits(B, 0, &I) < NeededSignBits)
02486     return nullptr;
02487 
02488   // In order to replace the original add with a narrower
02489   // llvm.sadd.with.overflow, the only uses allowed are the add-with-constant
02490   // and truncates that discard the high bits of the add.  Verify that this is
02491   // the case.
02492   Instruction *OrigAdd = cast<Instruction>(AddWithCst->getOperand(0));
02493   for (User *U : OrigAdd->users()) {
02494     if (U == AddWithCst) continue;
02495 
02496     // Only accept truncates for now.  We would really like a nice recursive
02497     // predicate like SimplifyDemandedBits, but which goes downwards the use-def
02498     // chain to see which bits of a value are actually demanded.  If the
02499     // original add had another add which was then immediately truncated, we
02500     // could still do the transformation.
02501     TruncInst *TI = dyn_cast<TruncInst>(U);
02502     if (!TI || TI->getType()->getPrimitiveSizeInBits() > NewWidth)
02503       return nullptr;
02504   }
02505 
02506   // If the pattern matches, truncate the inputs to the narrower type and
02507   // use the sadd_with_overflow intrinsic to efficiently compute both the
02508   // result and the overflow bit.
02509   Type *NewType = IntegerType::get(OrigAdd->getContext(), NewWidth);
02510   Value *F = Intrinsic::getDeclaration(I.getModule(),
02511                                        Intrinsic::sadd_with_overflow, NewType);
02512 
02513   InstCombiner::BuilderTy *Builder = IC.Builder;
02514 
02515   // Put the new code above the original add, in case there are any uses of the
02516   // add between the add and the compare.
02517   Builder->SetInsertPoint(OrigAdd);
02518 
02519   Value *TruncA = Builder->CreateTrunc(A, NewType, A->getName()+".trunc");
02520   Value *TruncB = Builder->CreateTrunc(B, NewType, B->getName()+".trunc");
02521   CallInst *Call = Builder->CreateCall(F, {TruncA, TruncB}, "sadd");
02522   Value *Add = Builder->CreateExtractValue(Call, 0, "sadd.result");
02523   Value *ZExt = Builder->CreateZExt(Add, OrigAdd->getType());
02524 
02525   // The inner add was the result of the narrow add, zero extended to the
02526   // wider type.  Replace it with the result computed by the intrinsic.
02527   IC.ReplaceInstUsesWith(*OrigAdd, ZExt);
02528 
02529   // The original icmp gets replaced with the overflow value.
02530   return ExtractValueInst::Create(Call, 1, "sadd.overflow");
02531 }
02532 
02533 bool InstCombiner::OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS,
02534                                          Value *RHS, Instruction &OrigI,
02535                                          Value *&Result, Constant *&Overflow) {
02536   if (OrigI.isCommutative() && isa<Constant>(LHS) && !isa<Constant>(RHS))
02537     std::swap(LHS, RHS);
02538 
02539   auto SetResult = [&](Value *OpResult, Constant *OverflowVal, bool ReuseName) {
02540     Result = OpResult;
02541     Overflow = OverflowVal;
02542     if (ReuseName)
02543       Result->takeName(&OrigI);
02544     return true;
02545   };
02546 
02547   // If the overflow check was an add followed by a compare, the insertion point
02548   // may be pointing to the compare.  We want to insert the new instructions
02549   // before the add in case there are uses of the add between the add and the
02550   // compare.
02551   Builder->SetInsertPoint(&OrigI);
02552 
02553   switch (OCF) {
02554   case OCF_INVALID:
02555     llvm_unreachable("bad overflow check kind!");
02556 
02557   case OCF_UNSIGNED_ADD: {
02558     OverflowResult OR = computeOverflowForUnsignedAdd(LHS, RHS, &OrigI);
02559     if (OR == OverflowResult::NeverOverflows)
02560       return SetResult(Builder->CreateNUWAdd(LHS, RHS), Builder->getFalse(),
02561                        true);
02562 
02563     if (OR == OverflowResult::AlwaysOverflows)
02564       return SetResult(Builder->CreateAdd(LHS, RHS), Builder->getTrue(), true);
02565   }
02566   // FALL THROUGH uadd into sadd
02567   case OCF_SIGNED_ADD: {
02568     // X + 0 -> {X, false}
02569     if (match(RHS, m_Zero()))
02570       return SetResult(LHS, Builder->getFalse(), false);
02571 
02572     // We can strength reduce this signed add into a regular add if we can prove
02573     // that it will never overflow.
02574     if (OCF == OCF_SIGNED_ADD)
02575       if (WillNotOverflowSignedAdd(LHS, RHS, OrigI))
02576         return SetResult(Builder->CreateNSWAdd(LHS, RHS), Builder->getFalse(),
02577                          true);
02578     break;
02579   }
02580 
02581   case OCF_UNSIGNED_SUB:
02582   case OCF_SIGNED_SUB: {
02583     // X - 0 -> {X, false}
02584     if (match(RHS, m_Zero()))
02585       return SetResult(LHS, Builder->getFalse(), false);
02586 
02587     if (OCF == OCF_SIGNED_SUB) {
02588       if (WillNotOverflowSignedSub(LHS, RHS, OrigI))
02589         return SetResult(Builder->CreateNSWSub(LHS, RHS), Builder->getFalse(),
02590                          true);
02591     } else {
02592       if (WillNotOverflowUnsignedSub(LHS, RHS, OrigI))
02593         return SetResult(Builder->CreateNUWSub(LHS, RHS), Builder->getFalse(),
02594                          true);
02595     }
02596     break;
02597   }
02598 
02599   case OCF_UNSIGNED_MUL: {
02600     OverflowResult OR = computeOverflowForUnsignedMul(LHS, RHS, &OrigI);
02601     if (OR == OverflowResult::NeverOverflows)
02602       return SetResult(Builder->CreateNUWMul(LHS, RHS), Builder->getFalse(),
02603                        true);
02604     if (OR == OverflowResult::AlwaysOverflows)
02605       return SetResult(Builder->CreateMul(LHS, RHS), Builder->getTrue(), true);
02606   } // FALL THROUGH
02607   case OCF_SIGNED_MUL:
02608     // X * undef -> undef
02609     if (isa<UndefValue>(RHS))
02610       return SetResult(RHS, UndefValue::get(Builder->getInt1Ty()), false);
02611 
02612     // X * 0 -> {0, false}
02613     if (match(RHS, m_Zero()))
02614       return SetResult(RHS, Builder->getFalse(), false);
02615 
02616     // X * 1 -> {X, false}
02617     if (match(RHS, m_One()))
02618       return SetResult(LHS, Builder->getFalse(), false);
02619 
02620     if (OCF == OCF_SIGNED_MUL)
02621       if (WillNotOverflowSignedMul(LHS, RHS, OrigI))
02622         return SetResult(Builder->CreateNSWMul(LHS, RHS), Builder->getFalse(),
02623                          true);
02624     break;
02625   }
02626 
02627   return false;
02628 }
02629 
02630 /// \brief Recognize and process idiom involving test for multiplication
02631 /// overflow.
02632 ///
02633 /// The caller has matched a pattern of the form:
02634 ///   I = cmp u (mul(zext A, zext B), V
02635 /// The function checks if this is a test for overflow and if so replaces
02636 /// multiplication with call to 'mul.with.overflow' intrinsic.
02637 ///
02638 /// \param I Compare instruction.
02639 /// \param MulVal Result of 'mult' instruction.  It is one of the arguments of
02640 ///               the compare instruction.  Must be of integer type.
02641 /// \param OtherVal The other argument of compare instruction.
02642 /// \returns Instruction which must replace the compare instruction, NULL if no
02643 ///          replacement required.
02644 static Instruction *ProcessUMulZExtIdiom(ICmpInst &I, Value *MulVal,
02645                                          Value *OtherVal, InstCombiner &IC) {
02646   // Don't bother doing this transformation for pointers, don't do it for
02647   // vectors.
02648   if (!isa<IntegerType>(MulVal->getType()))
02649     return nullptr;
02650 
02651   assert(I.getOperand(0) == MulVal || I.getOperand(1) == MulVal);
02652   assert(I.getOperand(0) == OtherVal || I.getOperand(1) == OtherVal);
02653   auto *MulInstr = dyn_cast<Instruction>(MulVal);
02654   if (!MulInstr)
02655     return nullptr;
02656   assert(MulInstr->getOpcode() == Instruction::Mul);
02657 
02658   auto *LHS = cast<ZExtOperator>(MulInstr->getOperand(0)),
02659        *RHS = cast<ZExtOperator>(MulInstr->getOperand(1));
02660   assert(LHS->getOpcode() == Instruction::ZExt);
02661   assert(RHS->getOpcode() == Instruction::ZExt);
02662   Value *A = LHS->getOperand(0), *B = RHS->getOperand(0);
02663 
02664   // Calculate type and width of the result produced by mul.with.overflow.
02665   Type *TyA = A->getType(), *TyB = B->getType();
02666   unsigned WidthA = TyA->getPrimitiveSizeInBits(),
02667            WidthB = TyB->getPrimitiveSizeInBits();
02668   unsigned MulWidth;
02669   Type *MulType;
02670   if (WidthB > WidthA) {
02671     MulWidth = WidthB;
02672     MulType = TyB;
02673   } else {
02674     MulWidth = WidthA;
02675     MulType = TyA;
02676   }
02677 
02678   // In order to replace the original mul with a narrower mul.with.overflow,
02679   // all uses must ignore upper bits of the product.  The number of used low
02680   // bits must be not greater than the width of mul.with.overflow.
02681   if (MulVal->hasNUsesOrMore(2))
02682     for (User *U : MulVal->users()) {
02683       if (U == &I)
02684         continue;
02685       if (TruncInst *TI = dyn_cast<TruncInst>(U)) {
02686         // Check if truncation ignores bits above MulWidth.
02687         unsigned TruncWidth = TI->getType()->getPrimitiveSizeInBits();
02688         if (TruncWidth > MulWidth)
02689           return nullptr;
02690       } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) {
02691         // Check if AND ignores bits above MulWidth.
02692         if (BO->getOpcode() != Instruction::And)
02693           return nullptr;
02694         if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
02695           const APInt &CVal = CI->getValue();
02696           if (CVal.getBitWidth() - CVal.countLeadingZeros() > MulWidth)
02697             return nullptr;
02698         }
02699       } else {
02700         // Other uses prohibit this transformation.
02701         return nullptr;
02702       }
02703     }
02704 
02705   // Recognize patterns
02706   switch (I.getPredicate()) {
02707   case ICmpInst::ICMP_EQ:
02708   case ICmpInst::ICMP_NE:
02709     // Recognize pattern:
02710     //   mulval = mul(zext A, zext B)
02711     //   cmp eq/neq mulval, zext trunc mulval
02712     if (ZExtInst *Zext = dyn_cast<ZExtInst>(OtherVal))
02713       if (Zext->hasOneUse()) {
02714         Value *ZextArg = Zext->getOperand(0);
02715         if (TruncInst *Trunc = dyn_cast<TruncInst>(ZextArg))
02716           if (Trunc->getType()->getPrimitiveSizeInBits() == MulWidth)
02717             break; //Recognized
02718       }
02719 
02720     // Recognize pattern:
02721     //   mulval = mul(zext A, zext B)
02722     //   cmp eq/neq mulval, and(mulval, mask), mask selects low MulWidth bits.
02723     ConstantInt *CI;
02724     Value *ValToMask;
02725     if (match(OtherVal, m_And(m_Value(ValToMask), m_ConstantInt(CI)))) {
02726       if (ValToMask != MulVal)
02727         return nullptr;
02728       const APInt &CVal = CI->getValue() + 1;
02729       if (CVal.isPowerOf2()) {
02730         unsigned MaskWidth = CVal.logBase2();
02731         if (MaskWidth == MulWidth)
02732           break; // Recognized
02733       }
02734     }
02735     return nullptr;
02736 
02737   case ICmpInst::ICMP_UGT:
02738     // Recognize pattern:
02739     //   mulval = mul(zext A, zext B)
02740     //   cmp ugt mulval, max
02741     if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
02742       APInt MaxVal = APInt::getMaxValue(MulWidth);
02743       MaxVal = MaxVal.zext(CI->getBitWidth());
02744       if (MaxVal.eq(CI->getValue()))
02745         break; // Recognized
02746     }
02747     return nullptr;
02748 
02749   case ICmpInst::ICMP_UGE:
02750     // Recognize pattern:
02751     //   mulval = mul(zext A, zext B)
02752     //   cmp uge mulval, max+1
02753     if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
02754       APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth);
02755       if (MaxVal.eq(CI->getValue()))
02756         break; // Recognized
02757     }
02758     return nullptr;
02759 
02760   case ICmpInst::ICMP_ULE:
02761     // Recognize pattern:
02762     //   mulval = mul(zext A, zext B)
02763     //   cmp ule mulval, max
02764     if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
02765       APInt MaxVal = APInt::getMaxValue(MulWidth);
02766       MaxVal = MaxVal.zext(CI->getBitWidth());
02767       if (MaxVal.eq(CI->getValue()))
02768         break; // Recognized
02769     }
02770     return nullptr;
02771 
02772   case ICmpInst::ICMP_ULT:
02773     // Recognize pattern:
02774     //   mulval = mul(zext A, zext B)
02775     //   cmp ule mulval, max + 1
02776     if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
02777       APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth);
02778       if (MaxVal.eq(CI->getValue()))
02779         break; // Recognized
02780     }
02781     return nullptr;
02782 
02783   default:
02784     return nullptr;
02785   }
02786 
02787   InstCombiner::BuilderTy *Builder = IC.Builder;
02788   Builder->SetInsertPoint(MulInstr);
02789 
02790   // Replace: mul(zext A, zext B) --> mul.with.overflow(A, B)
02791   Value *MulA = A, *MulB = B;
02792   if (WidthA < MulWidth)
02793     MulA = Builder->CreateZExt(A, MulType);
02794   if (WidthB < MulWidth)
02795     MulB = Builder->CreateZExt(B, MulType);
02796   Value *F = Intrinsic::getDeclaration(I.getModule(),
02797                                        Intrinsic::umul_with_overflow, MulType);
02798   CallInst *Call = Builder->CreateCall(F, {MulA, MulB}, "umul");
02799   IC.Worklist.Add(MulInstr);
02800 
02801   // If there are uses of mul result other than the comparison, we know that
02802   // they are truncation or binary AND. Change them to use result of
02803   // mul.with.overflow and adjust properly mask/size.
02804   if (MulVal->hasNUsesOrMore(2)) {
02805     Value *Mul = Builder->CreateExtractValue(Call, 0, "umul.value");
02806     for (User *U : MulVal->users()) {
02807       if (U == &I || U == OtherVal)
02808         continue;
02809       if (TruncInst *TI = dyn_cast<TruncInst>(U)) {
02810         if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
02811           IC.ReplaceInstUsesWith(*TI, Mul);
02812         else
02813           TI->setOperand(0, Mul);
02814       } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) {
02815         assert(BO->getOpcode() == Instruction::And);
02816         // Replace (mul & mask) --> zext (mul.with.overflow & short_mask)
02817         ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
02818         APInt ShortMask = CI->getValue().trunc(MulWidth);
02819         Value *ShortAnd = Builder->CreateAnd(Mul, ShortMask);
02820         Instruction *Zext =
02821             cast<Instruction>(Builder->CreateZExt(ShortAnd, BO->getType()));
02822         IC.Worklist.Add(Zext);
02823         IC.ReplaceInstUsesWith(*BO, Zext);
02824       } else {
02825         llvm_unreachable("Unexpected Binary operation");
02826       }
02827       IC.Worklist.Add(cast<Instruction>(U));
02828     }
02829   }
02830   if (isa<Instruction>(OtherVal))
02831     IC.Worklist.Add(cast<Instruction>(OtherVal));
02832 
02833   // The original icmp gets replaced with the overflow value, maybe inverted
02834   // depending on predicate.
02835   bool Inverse = false;
02836   switch (I.getPredicate()) {
02837   case ICmpInst::ICMP_NE:
02838     break;
02839   case ICmpInst::ICMP_EQ:
02840     Inverse = true;
02841     break;
02842   case ICmpInst::ICMP_UGT:
02843   case ICmpInst::ICMP_UGE:
02844     if (I.getOperand(0) == MulVal)
02845       break;
02846     Inverse = true;
02847     break;
02848   case ICmpInst::ICMP_ULT:
02849   case ICmpInst::ICMP_ULE:
02850     if (I.getOperand(1) == MulVal)
02851       break;
02852     Inverse = true;
02853     break;
02854   default:
02855     llvm_unreachable("Unexpected predicate");
02856   }
02857   if (Inverse) {
02858     Value *Res = Builder->CreateExtractValue(Call, 1);
02859     return BinaryOperator::CreateNot(Res);
02860   }
02861 
02862   return ExtractValueInst::Create(Call, 1);
02863 }
02864 
02865 // DemandedBitsLHSMask - When performing a comparison against a constant,
02866 // it is possible that not all the bits in the LHS are demanded.  This helper
02867 // method computes the mask that IS demanded.
02868 static APInt DemandedBitsLHSMask(ICmpInst &I,
02869                                  unsigned BitWidth, bool isSignCheck) {
02870   if (isSignCheck)
02871     return APInt::getSignBit(BitWidth);
02872 
02873   ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1));
02874   if (!CI) return APInt::getAllOnesValue(BitWidth);
02875   const APInt &RHS = CI->getValue();
02876 
02877   switch (I.getPredicate()) {
02878   // For a UGT comparison, we don't care about any bits that
02879   // correspond to the trailing ones of the comparand.  The value of these
02880   // bits doesn't impact the outcome of the comparison, because any value
02881   // greater than the RHS must differ in a bit higher than these due to carry.
02882   case ICmpInst::ICMP_UGT: {
02883     unsigned trailingOnes = RHS.countTrailingOnes();
02884     APInt lowBitsSet = APInt::getLowBitsSet(BitWidth, trailingOnes);
02885     return ~lowBitsSet;
02886   }
02887 
02888   // Similarly, for a ULT comparison, we don't care about the trailing zeros.
02889   // Any value less than the RHS must differ in a higher bit because of carries.
02890   case ICmpInst::ICMP_ULT: {
02891     unsigned trailingZeros = RHS.countTrailingZeros();
02892     APInt lowBitsSet = APInt::getLowBitsSet(BitWidth, trailingZeros);
02893     return ~lowBitsSet;
02894   }
02895 
02896   default:
02897     return APInt::getAllOnesValue(BitWidth);
02898   }
02899 }
02900 
02901 /// \brief Check if the order of \p Op0 and \p Op1 as operand in an ICmpInst
02902 /// should be swapped.
02903 /// The decision is based on how many times these two operands are reused
02904 /// as subtract operands and their positions in those instructions.
02905 /// The rational is that several architectures use the same instruction for
02906 /// both subtract and cmp, thus it is better if the order of those operands
02907 /// match.
02908 /// \return true if Op0 and Op1 should be swapped.
02909 static bool swapMayExposeCSEOpportunities(const Value * Op0,
02910                                           const Value * Op1) {
02911   // Filter out pointer value as those cannot appears directly in subtract.
02912   // FIXME: we may want to go through inttoptrs or bitcasts.
02913   if (Op0->getType()->isPointerTy())
02914     return false;
02915   // Count every uses of both Op0 and Op1 in a subtract.
02916   // Each time Op0 is the first operand, count -1: swapping is bad, the
02917   // subtract has already the same layout as the compare.
02918   // Each time Op0 is the second operand, count +1: swapping is good, the
02919   // subtract has a different layout as the compare.
02920   // At the end, if the benefit is greater than 0, Op0 should come second to
02921   // expose more CSE opportunities.
02922   int GlobalSwapBenefits = 0;
02923   for (const User *U : Op0->users()) {
02924     const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(U);
02925     if (!BinOp || BinOp->getOpcode() != Instruction::Sub)
02926       continue;
02927     // If Op0 is the first argument, this is not beneficial to swap the
02928     // arguments.
02929     int LocalSwapBenefits = -1;
02930     unsigned Op1Idx = 1;
02931     if (BinOp->getOperand(Op1Idx) == Op0) {
02932       Op1Idx = 0;
02933       LocalSwapBenefits = 1;
02934     }
02935     if (BinOp->getOperand(Op1Idx) != Op1)
02936       continue;
02937     GlobalSwapBenefits += LocalSwapBenefits;
02938   }
02939   return GlobalSwapBenefits > 0;
02940 }
02941 
02942 /// \brief Check that one use is in the same block as the definition and all
02943 /// other uses are in blocks dominated by a given block
02944 ///
02945 /// \param DI Definition
02946 /// \param UI Use
02947 /// \param DB Block that must dominate all uses of \p DI outside
02948 ///           the parent block
02949 /// \return true when \p UI is the only use of \p DI in the parent block
02950 /// and all other uses of \p DI are in blocks dominated by \p DB.
02951 ///
02952 bool InstCombiner::dominatesAllUses(const Instruction *DI,
02953                                     const Instruction *UI,
02954                                     const BasicBlock *DB) const {
02955   assert(DI && UI && "Instruction not defined\n");
02956   // ignore incomplete definitions
02957   if (!DI->getParent())
02958     return false;
02959   // DI and UI must be in the same block
02960   if (DI->getParent() != UI->getParent())
02961     return false;
02962   // Protect from self-referencing blocks
02963   if (DI->getParent() == DB)
02964     return false;
02965   // DominatorTree available?
02966   if (!DT)
02967     return false;
02968   for (const User *U : DI->users()) {
02969     auto *Usr = cast<Instruction>(U);
02970     if (Usr != UI && !DT->dominates(DB, Usr->getParent()))
02971       return false;
02972   }
02973   return true;
02974 }
02975 
02976 ///
02977 /// true when the instruction sequence within a block is select-cmp-br.
02978 ///
02979 static bool isChainSelectCmpBranch(const SelectInst *SI) {
02980   const BasicBlock *BB = SI->getParent();
02981   if (!BB)
02982     return false;
02983   auto *BI = dyn_cast_or_null<BranchInst>(BB->getTerminator());
02984   if (!BI || BI->getNumSuccessors() != 2)
02985     return false;
02986   auto *IC = dyn_cast<ICmpInst>(BI->getCondition());
02987   if (!IC || (IC->getOperand(0) != SI && IC->getOperand(1) != SI))
02988     return false;
02989   return true;
02990 }
02991 
02992 ///
02993 /// \brief True when a select result is replaced by one of its operands
02994 /// in select-icmp sequence. This will eventually result in the elimination
02995 /// of the select.
02996 ///
02997 /// \param SI    Select instruction
02998 /// \param Icmp  Compare instruction
02999 /// \param SIOpd Operand that replaces the select
03000 ///
03001 /// Notes:
03002 /// - The replacement is global and requires dominator information
03003 /// - The caller is responsible for the actual replacement
03004 ///
03005 /// Example:
03006 ///
03007 /// entry:
03008 ///  %4 = select i1 %3, %C* %0, %C* null
03009 ///  %5 = icmp eq %C* %4, null
03010 ///  br i1 %5, label %9, label %7
03011 ///  ...
03012 ///  ; <label>:7                                       ; preds = %entry
03013 ///  %8 = getelementptr inbounds %C* %4, i64 0, i32 0
03014 ///  ...
03015 ///
03016 /// can be transformed to
03017 ///
03018 ///  %5 = icmp eq %C* %0, null
03019 ///  %6 = select i1 %3, i1 %5, i1 true
03020 ///  br i1 %6, label %9, label %7
03021 ///  ...
03022 ///  ; <label>:7                                       ; preds = %entry
03023 ///  %8 = getelementptr inbounds %C* %0, i64 0, i32 0  // replace by %0!
03024 ///
03025 /// Similar when the first operand of the select is a constant or/and
03026 /// the compare is for not equal rather than equal.
03027 ///
03028 /// NOTE: The function is only called when the select and compare constants
03029 /// are equal, the optimization can work only for EQ predicates. This is not a
03030 /// major restriction since a NE compare should be 'normalized' to an equal
03031 /// compare, which usually happens in the combiner and test case
03032 /// select-cmp-br.ll
03033 /// checks for it.
03034 bool InstCombiner::replacedSelectWithOperand(SelectInst *SI,
03035                                              const ICmpInst *Icmp,
03036                                              const unsigned SIOpd) {
03037   assert((SIOpd == 1 || SIOpd == 2) && "Invalid select operand!");
03038   if (isChainSelectCmpBranch(SI) && Icmp->getPredicate() == ICmpInst::ICMP_EQ) {
03039     BasicBlock *Succ = SI->getParent()->getTerminator()->getSuccessor(1);
03040     // The check for the unique predecessor is not the best that can be
03041     // done. But it protects efficiently against cases like  when SI's
03042     // home block has two successors, Succ and Succ1, and Succ1 predecessor
03043     // of Succ. Then SI can't be replaced by SIOpd because the use that gets
03044     // replaced can be reached on either path. So the uniqueness check
03045     // guarantees that the path all uses of SI (outside SI's parent) are on
03046     // is disjoint from all other paths out of SI. But that information
03047     // is more expensive to compute, and the trade-off here is in favor
03048     // of compile-time.
03049     if (Succ->getUniquePredecessor() && dominatesAllUses(SI, Icmp, Succ)) {
03050       NumSel++;
03051       SI->replaceUsesOutsideBlock(SI->getOperand(SIOpd), SI->getParent());
03052       return true;
03053     }
03054   }
03055   return false;
03056 }
03057 
03058 Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
03059   bool Changed = false;
03060   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
03061   unsigned Op0Cplxity = getComplexity(Op0);
03062   unsigned Op1Cplxity = getComplexity(Op1);
03063 
03064   /// Orders the operands of the compare so that they are listed from most
03065   /// complex to least complex.  This puts constants before unary operators,
03066   /// before binary operators.
03067   if (Op0Cplxity < Op1Cplxity ||
03068         (Op0Cplxity == Op1Cplxity &&
03069          swapMayExposeCSEOpportunities(Op0, Op1))) {
03070     I.swapOperands();
03071     std::swap(Op0, Op1);
03072     Changed = true;
03073   }
03074 
03075   if (Value *V =
03076           SimplifyICmpInst(I.getPredicate(), Op0, Op1, DL, TLI, DT, AC, &I))
03077     return ReplaceInstUsesWith(I, V);
03078 
03079   // comparing -val or val with non-zero is the same as just comparing val
03080   // ie, abs(val) != 0 -> val != 0
03081   if (I.getPredicate() == ICmpInst::ICMP_NE && match(Op1, m_Zero()))
03082   {
03083     Value *Cond, *SelectTrue, *SelectFalse;
03084     if (match(Op0, m_Select(m_Value(Cond), m_Value(SelectTrue),
03085                             m_Value(SelectFalse)))) {
03086       if (Value *V = dyn_castNegVal(SelectTrue)) {
03087         if (V == SelectFalse)
03088           return CmpInst::Create(Instruction::ICmp, I.getPredicate(), V, Op1);
03089       }
03090       else if (Value *V = dyn_castNegVal(SelectFalse)) {
03091         if (V == SelectTrue)
03092           return CmpInst::Create(Instruction::ICmp, I.getPredicate(), V, Op1);
03093       }
03094     }
03095   }
03096 
03097   Type *Ty = Op0->getType();
03098 
03099   // icmp's with boolean values can always be turned into bitwise operations
03100   if (Ty->isIntegerTy(1)) {
03101     switch (I.getPredicate()) {
03102     default: llvm_unreachable("Invalid icmp instruction!");
03103     case ICmpInst::ICMP_EQ: {               // icmp eq i1 A, B -> ~(A^B)
03104       Value *Xor = Builder->CreateXor(Op0, Op1, I.getName()+"tmp");
03105       return BinaryOperator::CreateNot(Xor);
03106     }
03107     case ICmpInst::ICMP_NE:                  // icmp eq i1 A, B -> A^B
03108       return BinaryOperator::CreateXor(Op0, Op1);
03109 
03110     case ICmpInst::ICMP_UGT:
03111       std::swap(Op0, Op1);                   // Change icmp ugt -> icmp ult
03112       // FALL THROUGH
03113     case ICmpInst::ICMP_ULT:{               // icmp ult i1 A, B -> ~A & B
03114       Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
03115       return BinaryOperator::CreateAnd(Not, Op1);
03116     }
03117     case ICmpInst::ICMP_SGT:
03118       std::swap(Op0, Op1);                   // Change icmp sgt -> icmp slt
03119       // FALL THROUGH
03120     case ICmpInst::ICMP_SLT: {               // icmp slt i1 A, B -> A & ~B
03121       Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
03122       return BinaryOperator::CreateAnd(Not, Op0);
03123     }
03124     case ICmpInst::ICMP_UGE:
03125       std::swap(Op0, Op1);                   // Change icmp uge -> icmp ule
03126       // FALL THROUGH
03127     case ICmpInst::ICMP_ULE: {               //  icmp ule i1 A, B -> ~A | B
03128       Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
03129       return BinaryOperator::CreateOr(Not, Op1);
03130     }
03131     case ICmpInst::ICMP_SGE:
03132       std::swap(Op0, Op1);                   // Change icmp sge -> icmp sle
03133       // FALL THROUGH
03134     case ICmpInst::ICMP_SLE: {               //  icmp sle i1 A, B -> A | ~B
03135       Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
03136       return BinaryOperator::CreateOr(Not, Op0);
03137     }
03138     }
03139   }
03140 
03141   unsigned BitWidth = 0;
03142   if (Ty->isIntOrIntVectorTy())
03143     BitWidth = Ty->getScalarSizeInBits();
03144   else // Get pointer size.
03145     BitWidth = DL.getTypeSizeInBits(Ty->getScalarType());
03146 
03147   bool isSignBit = false;
03148 
03149   // See if we are doing a comparison with a constant.
03150   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
03151     Value *A = nullptr, *B = nullptr;
03152 
03153     // Match the following pattern, which is a common idiom when writing
03154     // overflow-safe integer arithmetic function.  The source performs an
03155     // addition in wider type, and explicitly checks for overflow using
03156     // comparisons against INT_MIN and INT_MAX.  Simplify this by using the
03157     // sadd_with_overflow intrinsic.
03158     //
03159     // TODO: This could probably be generalized to handle other overflow-safe
03160     // operations if we worked out the formulas to compute the appropriate
03161     // magic constants.
03162     //
03163     // sum = a + b
03164     // if (sum+128 >u 255)  ...  -> llvm.sadd.with.overflow.i8
03165     {
03166     ConstantInt *CI2;    // I = icmp ugt (add (add A, B), CI2), CI
03167     if (I.getPredicate() == ICmpInst::ICMP_UGT &&
03168         match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2))))
03169       if (Instruction *Res = ProcessUGT_ADDCST_ADD(I, A, B, CI2, CI, *this))
03170         return Res;
03171     }
03172 
03173     // The following transforms are only 'worth it' if the only user of the
03174     // subtraction is the icmp.
03175     if (Op0->hasOneUse()) {
03176       // (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B)
03177       if (I.isEquality() && CI->isZero() &&
03178           match(Op0, m_Sub(m_Value(A), m_Value(B))))
03179         return new ICmpInst(I.getPredicate(), A, B);
03180 
03181       // (icmp sgt (sub nsw A B), -1) -> (icmp sge A, B)
03182       if (I.getPredicate() == ICmpInst::ICMP_SGT && CI->isAllOnesValue() &&
03183           match(Op0, m_NSWSub(m_Value(A), m_Value(B))))
03184         return new ICmpInst(ICmpInst::ICMP_SGE, A, B);
03185 
03186       // (icmp sgt (sub nsw A B), 0) -> (icmp sgt A, B)
03187       if (I.getPredicate() == ICmpInst::ICMP_SGT && CI->isZero() &&
03188           match(Op0, m_NSWSub(m_Value(A), m_Value(B))))
03189         return new ICmpInst(ICmpInst::ICMP_SGT, A, B);
03190 
03191       // (icmp slt (sub nsw A B), 0) -> (icmp slt A, B)
03192       if (I.getPredicate() == ICmpInst::ICMP_SLT && CI->isZero() &&
03193           match(Op0, m_NSWSub(m_Value(A), m_Value(B))))
03194         return new ICmpInst(ICmpInst::ICMP_SLT, A, B);
03195 
03196       // (icmp slt (sub nsw A B), 1) -> (icmp sle A, B)
03197       if (I.getPredicate() == ICmpInst::ICMP_SLT && CI->isOne() &&
03198           match(Op0, m_NSWSub(m_Value(A), m_Value(B))))
03199         return new ICmpInst(ICmpInst::ICMP_SLE, A, B);
03200     }
03201 
03202     // If we have an icmp le or icmp ge instruction, turn it into the
03203     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
03204     // them being folded in the code below.  The SimplifyICmpInst code has
03205     // already handled the edge cases for us, so we just assert on them.
03206     switch (I.getPredicate()) {
03207     default: break;
03208     case ICmpInst::ICMP_ULE:
03209       assert(!CI->isMaxValue(false));                 // A <=u MAX -> TRUE
03210       return new ICmpInst(ICmpInst::ICMP_ULT, Op0,
03211                           Builder->getInt(CI->getValue()+1));
03212     case ICmpInst::ICMP_SLE:
03213       assert(!CI->isMaxValue(true));                  // A <=s MAX -> TRUE
03214       return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
03215                           Builder->getInt(CI->getValue()+1));
03216     case ICmpInst::ICMP_UGE:
03217       assert(!CI->isMinValue(false));                 // A >=u MIN -> TRUE
03218       return new ICmpInst(ICmpInst::ICMP_UGT, Op0,
03219                           Builder->getInt(CI->getValue()-1));
03220     case ICmpInst::ICMP_SGE:
03221       assert(!CI->isMinValue(true));                  // A >=s MIN -> TRUE
03222       return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
03223                           Builder->getInt(CI->getValue()-1));
03224     }
03225 
03226     if (I.isEquality()) {
03227       ConstantInt *CI2;
03228       if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
03229           match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
03230         // (icmp eq/ne (ashr/lshr const2, A), const1)
03231         if (Instruction *Inst = FoldICmpCstShrCst(I, Op0, A, CI, CI2))
03232           return Inst;
03233       }
03234       if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
03235         // (icmp eq/ne (shl const2, A), const1)
03236         if (Instruction *Inst = FoldICmpCstShlCst(I, Op0, A, CI, CI2))
03237           return Inst;
03238       }
03239     }
03240 
03241     // If this comparison is a normal comparison, it demands all
03242     // bits, if it is a sign bit comparison, it only demands the sign bit.
03243     bool UnusedBit;
03244     isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
03245   }
03246 
03247   // See if we can fold the comparison based on range information we can get
03248   // by checking whether bits are known to be zero or one in the input.
03249   if (BitWidth != 0) {
03250     APInt Op0KnownZero(BitWidth, 0), Op0KnownOne(BitWidth, 0);
03251     APInt Op1KnownZero(BitWidth, 0), Op1KnownOne(BitWidth, 0);
03252 
03253     if (SimplifyDemandedBits(I.getOperandUse(0),
03254                              DemandedBitsLHSMask(I, BitWidth, isSignBit),
03255                              Op0KnownZero, Op0KnownOne, 0))
03256       return &I;
03257     if (SimplifyDemandedBits(I.getOperandUse(1),
03258                              APInt::getAllOnesValue(BitWidth), Op1KnownZero,
03259                              Op1KnownOne, 0))
03260       return &I;
03261 
03262     // Given the known and unknown bits, compute a range that the LHS could be
03263     // in.  Compute the Min, Max and RHS values based on the known bits. For the
03264     // EQ and NE we use unsigned values.
03265     APInt Op0Min(BitWidth, 0), Op0Max(BitWidth, 0);
03266     APInt Op1Min(BitWidth, 0), Op1Max(BitWidth, 0);
03267     if (I.isSigned()) {
03268       ComputeSignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
03269                                              Op0Min, Op0Max);
03270       ComputeSignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
03271                                              Op1Min, Op1Max);
03272     } else {
03273       ComputeUnsignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
03274                                                Op0Min, Op0Max);
03275       ComputeUnsignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
03276                                                Op1Min, Op1Max);
03277     }
03278 
03279     // If Min and Max are known to be the same, then SimplifyDemandedBits
03280     // figured out that the LHS is a constant.  Just constant fold this now so
03281     // that code below can assume that Min != Max.
03282     if (!isa<Constant>(Op0) && Op0Min == Op0Max)
03283       return new ICmpInst(I.getPredicate(),
03284                           ConstantInt::get(Op0->getType(), Op0Min), Op1);
03285     if (!isa<Constant>(Op1) && Op1Min == Op1Max)
03286       return new ICmpInst(I.getPredicate(), Op0,
03287                           ConstantInt::get(Op1->getType(), Op1Min));
03288 
03289     // Based on the range information we know about the LHS, see if we can
03290     // simplify this comparison.  For example, (x&4) < 8 is always true.
03291     switch (I.getPredicate()) {
03292     default: llvm_unreachable("Unknown icmp opcode!");
03293     case ICmpInst::ICMP_EQ: {
03294       if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
03295         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03296 
03297       // If all bits are known zero except for one, then we know at most one
03298       // bit is set.   If the comparison is against zero, then this is a check
03299       // to see if *that* bit is set.
03300       APInt Op0KnownZeroInverted = ~Op0KnownZero;
03301       if (~Op1KnownZero == 0) {
03302         // If the LHS is an AND with the same constant, look through it.
03303         Value *LHS = nullptr;
03304         ConstantInt *LHSC = nullptr;
03305         if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) ||
03306             LHSC->getValue() != Op0KnownZeroInverted)
03307           LHS = Op0;
03308 
03309         // If the LHS is 1 << x, and we know the result is a power of 2 like 8,
03310         // then turn "((1 << x)&8) == 0" into "x != 3".
03311         // or turn "((1 << x)&7) == 0" into "x > 2".
03312         Value *X = nullptr;
03313         if (match(LHS, m_Shl(m_One(), m_Value(X)))) {
03314           APInt ValToCheck = Op0KnownZeroInverted;
03315           if (ValToCheck.isPowerOf2()) {
03316             unsigned CmpVal = ValToCheck.countTrailingZeros();
03317             return new ICmpInst(ICmpInst::ICMP_NE, X,
03318                                 ConstantInt::get(X->getType(), CmpVal));
03319           } else if ((++ValToCheck).isPowerOf2()) {
03320             unsigned CmpVal = ValToCheck.countTrailingZeros() - 1;
03321             return new ICmpInst(ICmpInst::ICMP_UGT, X,
03322                                 ConstantInt::get(X->getType(), CmpVal));
03323           }
03324         }
03325 
03326         // If the LHS is 8 >>u x, and we know the result is a power of 2 like 1,
03327         // then turn "((8 >>u x)&1) == 0" into "x != 3".
03328         const APInt *CI;
03329         if (Op0KnownZeroInverted == 1 &&
03330             match(LHS, m_LShr(m_Power2(CI), m_Value(X))))
03331           return new ICmpInst(ICmpInst::ICMP_NE, X,
03332                               ConstantInt::get(X->getType(),
03333                                                CI->countTrailingZeros()));
03334       }
03335       break;
03336     }
03337     case ICmpInst::ICMP_NE: {
03338       if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
03339         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03340 
03341       // If all bits are known zero except for one, then we know at most one
03342       // bit is set.   If the comparison is against zero, then this is a check
03343       // to see if *that* bit is set.
03344       APInt Op0KnownZeroInverted = ~Op0KnownZero;
03345       if (~Op1KnownZero == 0) {
03346         // If the LHS is an AND with the same constant, look through it.
03347         Value *LHS = nullptr;
03348         ConstantInt *LHSC = nullptr;
03349         if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) ||
03350             LHSC->getValue() != Op0KnownZeroInverted)
03351           LHS = Op0;
03352 
03353         // If the LHS is 1 << x, and we know the result is a power of 2 like 8,
03354         // then turn "((1 << x)&8) != 0" into "x == 3".
03355         // or turn "((1 << x)&7) != 0" into "x < 3".
03356         Value *X = nullptr;
03357         if (match(LHS, m_Shl(m_One(), m_Value(X)))) {
03358           APInt ValToCheck = Op0KnownZeroInverted;
03359           if (ValToCheck.isPowerOf2()) {
03360             unsigned CmpVal = ValToCheck.countTrailingZeros();
03361             return new ICmpInst(ICmpInst::ICMP_EQ, X,
03362                                 ConstantInt::get(X->getType(), CmpVal));
03363           } else if ((++ValToCheck).isPowerOf2()) {
03364             unsigned CmpVal = ValToCheck.countTrailingZeros();
03365             return new ICmpInst(ICmpInst::ICMP_ULT, X,
03366                                 ConstantInt::get(X->getType(), CmpVal));
03367           }
03368         }
03369 
03370         // If the LHS is 8 >>u x, and we know the result is a power of 2 like 1,
03371         // then turn "((8 >>u x)&1) != 0" into "x == 3".
03372         const APInt *CI;
03373         if (Op0KnownZeroInverted == 1 &&
03374             match(LHS, m_LShr(m_Power2(CI), m_Value(X))))
03375           return new ICmpInst(ICmpInst::ICMP_EQ, X,
03376                               ConstantInt::get(X->getType(),
03377                                                CI->countTrailingZeros()));
03378       }
03379       break;
03380     }
03381     case ICmpInst::ICMP_ULT:
03382       if (Op0Max.ult(Op1Min))          // A <u B -> true if max(A) < min(B)
03383         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03384       if (Op0Min.uge(Op1Max))          // A <u B -> false if min(A) >= max(B)
03385         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03386       if (Op1Min == Op0Max)            // A <u B -> A != B if max(A) == min(B)
03387         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
03388       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
03389         if (Op1Max == Op0Min+1)        // A <u C -> A == C-1 if min(A)+1 == C
03390           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
03391                               Builder->getInt(CI->getValue()-1));
03392 
03393         // (x <u 2147483648) -> (x >s -1)  -> true if sign bit clear
03394         if (CI->isMinValue(true))
03395           return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
03396                            Constant::getAllOnesValue(Op0->getType()));
03397       }
03398       break;
03399     case ICmpInst::ICMP_UGT:
03400       if (Op0Min.ugt(Op1Max))          // A >u B -> true if min(A) > max(B)
03401         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03402       if (Op0Max.ule(Op1Min))          // A >u B -> false if max(A) <= max(B)
03403         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03404 
03405       if (Op1Max == Op0Min)            // A >u B -> A != B if min(A) == max(B)
03406         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
03407       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
03408         if (Op1Min == Op0Max-1)        // A >u C -> A == C+1 if max(a)-1 == C
03409           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
03410                               Builder->getInt(CI->getValue()+1));
03411 
03412         // (x >u 2147483647) -> (x <s 0)  -> true if sign bit set
03413         if (CI->isMaxValue(true))
03414           return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
03415                               Constant::getNullValue(Op0->getType()));
03416       }
03417       break;
03418     case ICmpInst::ICMP_SLT:
03419       if (Op0Max.slt(Op1Min))          // A <s B -> true if max(A) < min(C)
03420         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03421       if (Op0Min.sge(Op1Max))          // A <s B -> false if min(A) >= max(C)
03422         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03423       if (Op1Min == Op0Max)            // A <s B -> A != B if max(A) == min(B)
03424         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
03425       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
03426         if (Op1Max == Op0Min+1)        // A <s C -> A == C-1 if min(A)+1 == C
03427           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
03428                               Builder->getInt(CI->getValue()-1));
03429       }
03430       break;
03431     case ICmpInst::ICMP_SGT:
03432       if (Op0Min.sgt(Op1Max))          // A >s B -> true if min(A) > max(B)
03433         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03434       if (Op0Max.sle(Op1Min))          // A >s B -> false if max(A) <= min(B)
03435         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03436 
03437       if (Op1Max == Op0Min)            // A >s B -> A != B if min(A) == max(B)
03438         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
03439       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
03440         if (Op1Min == Op0Max-1)        // A >s C -> A == C+1 if max(A)-1 == C
03441           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
03442                               Builder->getInt(CI->getValue()+1));
03443       }
03444       break;
03445     case ICmpInst::ICMP_SGE:
03446       assert(!isa<ConstantInt>(Op1) && "ICMP_SGE with ConstantInt not folded!");
03447       if (Op0Min.sge(Op1Max))          // A >=s B -> true if min(A) >= max(B)
03448         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03449       if (Op0Max.slt(Op1Min))          // A >=s B -> false if max(A) < min(B)
03450         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03451       break;
03452     case ICmpInst::ICMP_SLE:
03453       assert(!isa<ConstantInt>(Op1) && "ICMP_SLE with ConstantInt not folded!");
03454       if (Op0Max.sle(Op1Min))          // A <=s B -> true if max(A) <= min(B)
03455         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03456       if (Op0Min.sgt(Op1Max))          // A <=s B -> false if min(A) > max(B)
03457         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03458       break;
03459     case ICmpInst::ICMP_UGE:
03460       assert(!isa<ConstantInt>(Op1) && "ICMP_UGE with ConstantInt not folded!");
03461       if (Op0Min.uge(Op1Max))          // A >=u B -> true if min(A) >= max(B)
03462         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03463       if (Op0Max.ult(Op1Min))          // A >=u B -> false if max(A) < min(B)
03464         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03465       break;
03466     case ICmpInst::ICMP_ULE:
03467       assert(!isa<ConstantInt>(Op1) && "ICMP_ULE with ConstantInt not folded!");
03468       if (Op0Max.ule(Op1Min))          // A <=u B -> true if max(A) <= min(B)
03469         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03470       if (Op0Min.ugt(Op1Max))          // A <=u B -> false if min(A) > max(B)
03471         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03472       break;
03473     }
03474 
03475     // Turn a signed comparison into an unsigned one if both operands
03476     // are known to have the same sign.
03477     if (I.isSigned() &&
03478         ((Op0KnownZero.isNegative() && Op1KnownZero.isNegative()) ||
03479          (Op0KnownOne.isNegative() && Op1KnownOne.isNegative())))
03480       return new ICmpInst(I.getUnsignedPredicate(), Op0, Op1);
03481   }
03482 
03483   // Test if the ICmpInst instruction is used exclusively by a select as
03484   // part of a minimum or maximum operation. If so, refrain from doing
03485   // any other folding. This helps out other analyses which understand
03486   // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
03487   // and CodeGen. And in this case, at least one of the comparison
03488   // operands has at least one user besides the compare (the select),
03489   // which would often largely negate the benefit of folding anyway.
03490   if (I.hasOneUse())
03491     if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin()))
03492       if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
03493           (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
03494         return nullptr;
03495 
03496   // See if we are doing a comparison between a constant and an instruction that
03497   // can be folded into the comparison.
03498   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
03499     // Since the RHS is a ConstantInt (CI), if the left hand side is an
03500     // instruction, see if that instruction also has constants so that the
03501     // instruction can be folded into the icmp
03502     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
03503       if (Instruction *Res = visitICmpInstWithInstAndIntCst(I, LHSI, CI))
03504         return Res;
03505   }
03506 
03507   // Handle icmp with constant (but not simple integer constant) RHS
03508   if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
03509     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
03510       switch (LHSI->getOpcode()) {
03511       case Instruction::GetElementPtr:
03512           // icmp pred GEP (P, int 0, int 0, int 0), null -> icmp pred P, null
03513         if (RHSC->isNullValue() &&
03514             cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
03515           return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
03516                   Constant::getNullValue(LHSI->getOperand(0)->getType()));
03517         break;
03518       case Instruction::PHI:
03519         // Only fold icmp into the PHI if the phi and icmp are in the same
03520         // block.  If in the same block, we're encouraging jump threading.  If
03521         // not, we are just pessimizing the code by making an i1 phi.
03522         if (LHSI->getParent() == I.getParent())
03523           if (Instruction *NV = FoldOpIntoPhi(I))
03524             return NV;
03525         break;
03526       case Instruction::Select: {
03527         // If either operand of the select is a constant, we can fold the
03528         // comparison into the select arms, which will cause one to be
03529         // constant folded and the select turned into a bitwise or.
03530         Value *Op1 = nullptr, *Op2 = nullptr;
03531         ConstantInt *CI = nullptr;
03532         if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
03533           Op1 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
03534           CI = dyn_cast<ConstantInt>(Op1);
03535         }
03536         if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
03537           Op2 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
03538           CI = dyn_cast<ConstantInt>(Op2);
03539         }
03540 
03541         // We only want to perform this transformation if it will not lead to
03542         // additional code. This is true if either both sides of the select
03543         // fold to a constant (in which case the icmp is replaced with a select
03544         // which will usually simplify) or this is the only user of the
03545         // select (in which case we are trading a select+icmp for a simpler
03546         // select+icmp) or all uses of the select can be replaced based on
03547         // dominance information ("Global cases").
03548         bool Transform = false;
03549         if (Op1 && Op2)
03550           Transform = true;
03551         else if (Op1 || Op2) {
03552           // Local case
03553           if (LHSI->hasOneUse())
03554             Transform = true;
03555           // Global cases
03556           else if (CI && !CI->isZero())
03557             // When Op1 is constant try replacing select with second operand.
03558             // Otherwise Op2 is constant and try replacing select with first
03559             // operand.
03560             Transform = replacedSelectWithOperand(cast<SelectInst>(LHSI), &I,
03561                                                   Op1 ? 2 : 1);
03562         }
03563         if (Transform) {
03564           if (!Op1)
03565             Op1 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(1),
03566                                       RHSC, I.getName());
03567           if (!Op2)
03568             Op2 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(2),
03569                                       RHSC, I.getName());
03570           return SelectInst::Create(LHSI->getOperand(0), Op1, Op2);
03571         }
03572         break;
03573       }
03574       case Instruction::IntToPtr:
03575         // icmp pred inttoptr(X), null -> icmp pred X, 0
03576         if (RHSC->isNullValue() &&
03577             DL.getIntPtrType(RHSC->getType()) == LHSI->getOperand(0)->getType())
03578           return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
03579                         Constant::getNullValue(LHSI->getOperand(0)->getType()));
03580         break;
03581 
03582       case Instruction::Load:
03583         // Try to optimize things like "A[i] > 4" to index computations.
03584         if (GetElementPtrInst *GEP =
03585               dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
03586           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
03587             if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
03588                 !cast<LoadInst>(LHSI)->isVolatile())
03589               if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
03590                 return Res;
03591         }
03592         break;
03593       }
03594   }
03595 
03596   // If we can optimize a 'icmp GEP, P' or 'icmp P, GEP', do so now.
03597   if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op0))
03598     if (Instruction *NI = FoldGEPICmp(GEP, Op1, I.getPredicate(), I))
03599       return NI;
03600   if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op1))
03601     if (Instruction *NI = FoldGEPICmp(GEP, Op0,
03602                            ICmpInst::getSwappedPredicate(I.getPredicate()), I))
03603       return NI;
03604 
03605   // Try to optimize equality comparisons against alloca-based pointers.
03606   if (Op0->getType()->isPointerTy() && I.isEquality()) {
03607     assert(Op1->getType()->isPointerTy() && "Comparing pointer with non-pointer?");
03608     if (auto *Alloca = dyn_cast<AllocaInst>(GetUnderlyingObject(Op0, DL)))
03609       if (Instruction *New = FoldAllocaCmp(I, Alloca, Op1))
03610         return New;
03611     if (auto *Alloca = dyn_cast<AllocaInst>(GetUnderlyingObject(Op1, DL)))
03612       if (Instruction *New = FoldAllocaCmp(I, Alloca, Op0))
03613         return New;
03614   }
03615 
03616   // Test to see if the operands of the icmp are casted versions of other
03617   // values.  If the ptr->ptr cast can be stripped off both arguments, we do so
03618   // now.
03619   if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) {
03620     if (Op0->getType()->isPointerTy() &&
03621         (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
03622       // We keep moving the cast from the left operand over to the right
03623       // operand, where it can often be eliminated completely.
03624       Op0 = CI->getOperand(0);
03625 
03626       // If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast
03627       // so eliminate it as well.
03628       if (BitCastInst *CI2 = dyn_cast<BitCastInst>(Op1))
03629         Op1 = CI2->getOperand(0);
03630 
03631       // If Op1 is a constant, we can fold the cast into the constant.
03632       if (Op0->getType() != Op1->getType()) {
03633         if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
03634           Op1 = ConstantExpr::getBitCast(Op1C, Op0->getType());
03635         } else {
03636           // Otherwise, cast the RHS right before the icmp
03637           Op1 = Builder->CreateBitCast(Op1, Op0->getType());
03638         }
03639       }
03640       return new ICmpInst(I.getPredicate(), Op0, Op1);
03641     }
03642   }
03643 
03644   if (isa<CastInst>(Op0)) {
03645     // Handle the special case of: icmp (cast bool to X), <cst>
03646     // This comes up when you have code like
03647     //   int X = A < B;
03648     //   if (X) ...
03649     // For generality, we handle any zero-extension of any operand comparison
03650     // with a constant or another cast from the same type.
03651     if (isa<Constant>(Op1) || isa<CastInst>(Op1))
03652       if (Instruction *R = visitICmpInstWithCastAndCast(I))
03653         return R;
03654   }
03655 
03656   // Special logic for binary operators.
03657   BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Op0);
03658   BinaryOperator *BO1 = dyn_cast<BinaryOperator>(Op1);
03659   if (BO0 || BO1) {
03660     CmpInst::Predicate Pred = I.getPredicate();
03661     bool NoOp0WrapProblem = false, NoOp1WrapProblem = false;
03662     if (BO0 && isa<OverflowingBinaryOperator>(BO0))
03663       NoOp0WrapProblem = ICmpInst::isEquality(Pred) ||
03664         (CmpInst::isUnsigned(Pred) && BO0->hasNoUnsignedWrap()) ||
03665         (CmpInst::isSigned(Pred) && BO0->hasNoSignedWrap());
03666     if (BO1 && isa<OverflowingBinaryOperator>(BO1))
03667       NoOp1WrapProblem = ICmpInst::isEquality(Pred) ||
03668         (CmpInst::isUnsigned(Pred) && BO1->hasNoUnsignedWrap()) ||
03669         (CmpInst::isSigned(Pred) && BO1->hasNoSignedWrap());
03670 
03671     // Analyze the case when either Op0 or Op1 is an add instruction.
03672     // Op0 = A + B (or A and B are null); Op1 = C + D (or C and D are null).
03673     Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
03674     if (BO0 && BO0->getOpcode() == Instruction::Add)
03675       A = BO0->getOperand(0), B = BO0->getOperand(1);
03676     if (BO1 && BO1->getOpcode() == Instruction::Add)
03677       C = BO1->getOperand(0), D = BO1->getOperand(1);
03678 
03679     // icmp (X+cst) < 0 --> X < -cst
03680     if (NoOp0WrapProblem && ICmpInst::isSigned(Pred) && match(Op1, m_Zero()))
03681       if (ConstantInt *RHSC = dyn_cast_or_null<ConstantInt>(B))
03682         if (!RHSC->isMinValue(/*isSigned=*/true))
03683           return new ICmpInst(Pred, A, ConstantExpr::getNeg(RHSC));
03684 
03685     // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
03686     if ((A == Op1 || B == Op1) && NoOp0WrapProblem)
03687       return new ICmpInst(Pred, A == Op1 ? B : A,
03688                           Constant::getNullValue(Op1->getType()));
03689 
03690     // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
03691     if ((C == Op0 || D == Op0) && NoOp1WrapProblem)
03692       return new ICmpInst(Pred, Constant::getNullValue(Op0->getType()),
03693                           C == Op0 ? D : C);
03694 
03695     // icmp (X+Y), (X+Z) -> icmp Y, Z for equalities or if there is no overflow.
03696     if (A && C && (A == C || A == D || B == C || B == D) &&
03697         NoOp0WrapProblem && NoOp1WrapProblem &&
03698         // Try not to increase register pressure.
03699         BO0->hasOneUse() && BO1->hasOneUse()) {
03700       // Determine Y and Z in the form icmp (X+Y), (X+Z).
03701       Value *Y, *Z;
03702       if (A == C) {
03703         // C + B == C + D  ->  B == D
03704         Y = B;
03705         Z = D;
03706       } else if (A == D) {
03707         // D + B == C + D  ->  B == C
03708         Y = B;
03709         Z = C;
03710       } else if (B == C) {
03711         // A + C == C + D  ->  A == D
03712         Y = A;
03713         Z = D;
03714       } else {
03715         assert(B == D);
03716         // A + D == C + D  ->  A == C
03717         Y = A;
03718         Z = C;
03719       }
03720       return new ICmpInst(Pred, Y, Z);
03721     }
03722 
03723     // icmp slt (X + -1), Y -> icmp sle X, Y
03724     if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SLT &&
03725         match(B, m_AllOnes()))
03726       return new ICmpInst(CmpInst::ICMP_SLE, A, Op1);
03727 
03728     // icmp sge (X + -1), Y -> icmp sgt X, Y
03729     if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SGE &&
03730         match(B, m_AllOnes()))
03731       return new ICmpInst(CmpInst::ICMP_SGT, A, Op1);
03732 
03733     // icmp sle (X + 1), Y -> icmp slt X, Y
03734     if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SLE &&
03735         match(B, m_One()))
03736       return new ICmpInst(CmpInst::ICMP_SLT, A, Op1);
03737 
03738     // icmp sgt (X + 1), Y -> icmp sge X, Y
03739     if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SGT &&
03740         match(B, m_One()))
03741       return new ICmpInst(CmpInst::ICMP_SGE, A, Op1);
03742 
03743     // icmp sgt X, (Y + -1) -> icmp sge X, Y
03744     if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_SGT &&
03745         match(D, m_AllOnes()))
03746       return new ICmpInst(CmpInst::ICMP_SGE, Op0, C);
03747 
03748     // icmp sle X, (Y + -1) -> icmp slt X, Y
03749     if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_SLE &&
03750         match(D, m_AllOnes()))
03751       return new ICmpInst(CmpInst::ICMP_SLT, Op0, C);
03752 
03753     // icmp sge X, (Y + 1) -> icmp sgt X, Y
03754     if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_SGE &&
03755         match(D, m_One()))
03756       return new ICmpInst(CmpInst::ICMP_SGT, Op0, C);
03757 
03758     // icmp slt X, (Y + 1) -> icmp sle X, Y
03759     if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_SLT &&
03760         match(D, m_One()))
03761       return new ICmpInst(CmpInst::ICMP_SLE, Op0, C);
03762 
03763     // if C1 has greater magnitude than C2:
03764     //  icmp (X + C1), (Y + C2) -> icmp (X + C3), Y
03765     //  s.t. C3 = C1 - C2
03766     //
03767     // if C2 has greater magnitude than C1:
03768     //  icmp (X + C1), (Y + C2) -> icmp X, (Y + C3)
03769     //  s.t. C3 = C2 - C1
03770     if (A && C && NoOp0WrapProblem && NoOp1WrapProblem &&
03771         (BO0->hasOneUse() || BO1->hasOneUse()) && !I.isUnsigned())
03772       if (ConstantInt *C1 = dyn_cast<ConstantInt>(B))
03773         if (ConstantInt *C2 = dyn_cast<ConstantInt>(D)) {
03774           const APInt &AP1 = C1->getValue();
03775           const APInt &AP2 = C2->getValue();
03776           if (AP1.isNegative() == AP2.isNegative()) {
03777             APInt AP1Abs = C1->getValue().abs();
03778             APInt AP2Abs = C2->getValue().abs();
03779             if (AP1Abs.uge(AP2Abs)) {
03780               ConstantInt *C3 = Builder->getInt(AP1 - AP2);
03781               Value *NewAdd = Builder->CreateNSWAdd(A, C3);
03782               return new ICmpInst(Pred, NewAdd, C);
03783             } else {
03784               ConstantInt *C3 = Builder->getInt(AP2 - AP1);
03785               Value *NewAdd = Builder->CreateNSWAdd(C, C3);
03786               return new ICmpInst(Pred, A, NewAdd);
03787             }
03788           }
03789         }
03790 
03791 
03792     // Analyze the case when either Op0 or Op1 is a sub instruction.
03793     // Op0 = A - B (or A and B are null); Op1 = C - D (or C and D are null).
03794     A = nullptr; B = nullptr; C = nullptr; D = nullptr;
03795     if (BO0 && BO0->getOpcode() == Instruction::Sub)
03796       A = BO0->getOperand(0), B = BO0->getOperand(1);
03797     if (BO1 && BO1->getOpcode() == Instruction::Sub)
03798       C = BO1->getOperand(0), D = BO1->getOperand(1);
03799 
03800     // icmp (X-Y), X -> icmp 0, Y for equalities or if there is no overflow.
03801     if (A == Op1 && NoOp0WrapProblem)
03802       return new ICmpInst(Pred, Constant::getNullValue(Op1->getType()), B);
03803 
03804     // icmp X, (X-Y) -> icmp Y, 0 for equalities or if there is no overflow.
03805     if (C == Op0 && NoOp1WrapProblem)
03806       return new ICmpInst(Pred, D, Constant::getNullValue(Op0->getType()));
03807 
03808     // icmp (Y-X), (Z-X) -> icmp Y, Z for equalities or if there is no overflow.
03809     if (B && D && B == D && NoOp0WrapProblem && NoOp1WrapProblem &&
03810         // Try not to increase register pressure.
03811         BO0->hasOneUse() && BO1->hasOneUse())
03812       return new ICmpInst(Pred, A, C);
03813 
03814     // icmp (X-Y), (X-Z) -> icmp Z, Y for equalities or if there is no overflow.
03815     if (A && C && A == C && NoOp0WrapProblem && NoOp1WrapProblem &&
03816         // Try not to increase register pressure.
03817         BO0->hasOneUse() && BO1->hasOneUse())
03818       return new ICmpInst(Pred, D, B);
03819 
03820     // icmp (0-X) < cst --> x > -cst
03821     if (NoOp0WrapProblem && ICmpInst::isSigned(Pred)) {
03822       Value *X;
03823       if (match(BO0, m_Neg(m_Value(X))))
03824         if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1))
03825           if (!RHSC->isMinValue(/*isSigned=*/true))
03826             return new ICmpInst(I.getSwappedPredicate(), X,
03827                                 ConstantExpr::getNeg(RHSC));
03828     }
03829 
03830     BinaryOperator *SRem = nullptr;
03831     // icmp (srem X, Y), Y
03832     if (BO0 && BO0->getOpcode() == Instruction::SRem &&
03833         Op1 == BO0->getOperand(1))
03834       SRem = BO0;
03835     // icmp Y, (srem X, Y)
03836     else if (BO1 && BO1->getOpcode() == Instruction::SRem &&
03837              Op0 == BO1->getOperand(1))
03838       SRem = BO1;
03839     if (SRem) {
03840       // We don't check hasOneUse to avoid increasing register pressure because
03841       // the value we use is the same value this instruction was already using.
03842       switch (SRem == BO0 ? ICmpInst::getSwappedPredicate(Pred) : Pred) {
03843         default: break;
03844         case ICmpInst::ICMP_EQ:
03845           return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
03846         case ICmpInst::ICMP_NE:
03847           return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
03848         case ICmpInst::ICMP_SGT:
03849         case ICmpInst::ICMP_SGE:
03850           return new ICmpInst(ICmpInst::ICMP_SGT, SRem->getOperand(1),
03851                               Constant::getAllOnesValue(SRem->getType()));
03852         case ICmpInst::ICMP_SLT:
03853         case ICmpInst::ICMP_SLE:
03854           return new ICmpInst(ICmpInst::ICMP_SLT, SRem->getOperand(1),
03855                               Constant::getNullValue(SRem->getType()));
03856       }
03857     }
03858 
03859     if (BO0 && BO1 && BO0->getOpcode() == BO1->getOpcode() &&
03860         BO0->hasOneUse() && BO1->hasOneUse() &&
03861         BO0->getOperand(1) == BO1->getOperand(1)) {
03862       switch (BO0->getOpcode()) {
03863       default: break;
03864       case Instruction::Add:
03865       case Instruction::Sub:
03866       case Instruction::Xor:
03867         if (I.isEquality())    // a+x icmp eq/ne b+x --> a icmp b
03868           return new ICmpInst(I.getPredicate(), BO0->getOperand(0),
03869                               BO1->getOperand(0));
03870         // icmp u/s (a ^ signbit), (b ^ signbit) --> icmp s/u a, b
03871         if (ConstantInt *CI = dyn_cast<ConstantInt>(BO0->getOperand(1))) {
03872           if (CI->getValue().isSignBit()) {
03873             ICmpInst::Predicate Pred = I.isSigned()
03874                                            ? I.getUnsignedPredicate()
03875                                            : I.getSignedPredicate();
03876             return new ICmpInst(Pred, BO0->getOperand(0),
03877                                 BO1->getOperand(0));
03878           }
03879 
03880           if (CI->isMaxValue(true)) {
03881             ICmpInst::Predicate Pred = I.isSigned()
03882                                            ? I.getUnsignedPredicate()
03883                                            : I.getSignedPredicate();
03884             Pred = I.getSwappedPredicate(Pred);
03885             return new ICmpInst(Pred, BO0->getOperand(0),
03886                                 BO1->getOperand(0));
03887           }
03888         }
03889         break;
03890       case Instruction::Mul:
03891         if (!I.isEquality())
03892           break;
03893 
03894         if (ConstantInt *CI = dyn_cast<ConstantInt>(BO0->getOperand(1))) {
03895           // a * Cst icmp eq/ne b * Cst --> a & Mask icmp b & Mask
03896           // Mask = -1 >> count-trailing-zeros(Cst).
03897           if (!CI->isZero() && !CI->isOne()) {
03898             const APInt &AP = CI->getValue();
03899             ConstantInt *Mask = ConstantInt::get(I.getContext(),
03900                                     APInt::getLowBitsSet(AP.getBitWidth(),
03901                                                          AP.getBitWidth() -
03902                                                     AP.countTrailingZeros()));
03903             Value *And1 = Builder->CreateAnd(BO0->getOperand(0), Mask);
03904             Value *And2 = Builder->CreateAnd(BO1->getOperand(0), Mask);
03905             return new ICmpInst(I.getPredicate(), And1, And2);
03906           }
03907         }
03908         break;
03909       case Instruction::UDiv:
03910       case Instruction::LShr:
03911         if (I.isSigned())
03912           break;
03913         // fall-through
03914       case Instruction::SDiv:
03915       case Instruction::AShr:
03916         if (!BO0->isExact() || !BO1->isExact())
03917           break;
03918         return new ICmpInst(I.getPredicate(), BO0->getOperand(0),
03919                             BO1->getOperand(0));
03920       case Instruction::Shl: {
03921         bool NUW = BO0->hasNoUnsignedWrap() && BO1->hasNoUnsignedWrap();
03922         bool NSW = BO0->hasNoSignedWrap() && BO1->hasNoSignedWrap();
03923         if (!NUW && !NSW)
03924           break;
03925         if (!NSW && I.isSigned())
03926           break;
03927         return new ICmpInst(I.getPredicate(), BO0->getOperand(0),
03928                             BO1->getOperand(0));
03929       }
03930       }
03931     }
03932 
03933     if (BO0) {
03934       // Transform  A & (L - 1) `ult` L --> L != 0
03935       auto LSubOne = m_Add(m_Specific(Op1), m_AllOnes());
03936       auto BitwiseAnd =
03937           m_CombineOr(m_And(m_Value(), LSubOne), m_And(LSubOne, m_Value()));
03938 
03939       if (match(BO0, BitwiseAnd) && I.getPredicate() == ICmpInst::ICMP_ULT) {
03940         auto *Zero = Constant::getNullValue(BO0->getType());
03941         return new ICmpInst(ICmpInst::ICMP_NE, Op1, Zero);
03942       }
03943     }
03944   }
03945 
03946   { Value *A, *B;
03947     // Transform (A & ~B) == 0 --> (A & B) != 0
03948     // and       (A & ~B) != 0 --> (A & B) == 0
03949     // if A is a power of 2.
03950     if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
03951         match(Op1, m_Zero()) &&
03952         isKnownToBeAPowerOfTwo(A, DL, false, 0, AC, &I, DT) && I.isEquality())
03953       return new ICmpInst(I.getInversePredicate(),
03954                           Builder->CreateAnd(A, B),
03955                           Op1);
03956 
03957     // ~x < ~y --> y < x
03958     // ~x < cst --> ~cst < x
03959     if (match(Op0, m_Not(m_Value(A)))) {
03960       if (match(Op1, m_Not(m_Value(B))))
03961         return new ICmpInst(I.getPredicate(), B, A);
03962       if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1))
03963         return new ICmpInst(I.getPredicate(), ConstantExpr::getNot(RHSC), A);
03964     }
03965 
03966     Instruction *AddI = nullptr;
03967     if (match(&I, m_UAddWithOverflow(m_Value(A), m_Value(B),
03968                                      m_Instruction(AddI))) &&
03969         isa<IntegerType>(A->getType())) {
03970       Value *Result;
03971       Constant *Overflow;
03972       if (OptimizeOverflowCheck(OCF_UNSIGNED_ADD, A, B, *AddI, Result,
03973                                 Overflow)) {
03974         ReplaceInstUsesWith(*AddI, Result);
03975         return ReplaceInstUsesWith(I, Overflow);
03976       }
03977     }
03978 
03979     // (zext a) * (zext b)  --> llvm.umul.with.overflow.
03980     if (match(Op0, m_Mul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) {
03981       if (Instruction *R = ProcessUMulZExtIdiom(I, Op0, Op1, *this))
03982         return R;
03983     }
03984     if (match(Op1, m_Mul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) {
03985       if (Instruction *R = ProcessUMulZExtIdiom(I, Op1, Op0, *this))
03986         return R;
03987     }
03988   }
03989 
03990   if (I.isEquality()) {
03991     Value *A, *B, *C, *D;
03992 
03993     if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) {
03994       if (A == Op1 || B == Op1) {    // (A^B) == A  ->  B == 0
03995         Value *OtherVal = A == Op1 ? B : A;
03996         return new ICmpInst(I.getPredicate(), OtherVal,
03997                             Constant::getNullValue(A->getType()));
03998       }
03999 
04000       if (match(Op1, m_Xor(m_Value(C), m_Value(D)))) {
04001         // A^c1 == C^c2 --> A == C^(c1^c2)
04002         ConstantInt *C1, *C2;
04003         if (match(B, m_ConstantInt(C1)) &&
04004             match(D, m_ConstantInt(C2)) && Op1->hasOneUse()) {
04005           Constant *NC = Builder->getInt(C1->getValue() ^ C2->getValue());
04006           Value *Xor = Builder->CreateXor(C, NC);
04007           return new ICmpInst(I.getPredicate(), A, Xor);
04008         }
04009 
04010         // A^B == A^D -> B == D
04011         if (A == C) return new ICmpInst(I.getPredicate(), B, D);
04012         if (A == D) return new ICmpInst(I.getPredicate(), B, C);
04013         if (B == C) return new ICmpInst(I.getPredicate(), A, D);
04014         if (B == D) return new ICmpInst(I.getPredicate(), A, C);
04015       }
04016     }
04017 
04018     if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
04019         (A == Op0 || B == Op0)) {
04020       // A == (A^B)  ->  B == 0
04021       Value *OtherVal = A == Op0 ? B : A;
04022       return new ICmpInst(I.getPredicate(), OtherVal,
04023                           Constant::getNullValue(A->getType()));
04024     }
04025 
04026     // (X&Z) == (Y&Z) -> (X^Y) & Z == 0
04027     if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B)))) &&
04028         match(Op1, m_OneUse(m_And(m_Value(C), m_Value(D))))) {
04029       Value *X = nullptr, *Y = nullptr, *Z = nullptr;
04030 
04031       if (A == C) {
04032         X = B; Y = D; Z = A;
04033       } else if (A == D) {
04034         X = B; Y = C; Z = A;
04035       } else if (B == C) {
04036         X = A; Y = D; Z = B;
04037       } else if (B == D) {
04038         X = A; Y = C; Z = B;
04039       }
04040 
04041       if (X) {   // Build (X^Y) & Z
04042         Op1 = Builder->CreateXor(X, Y);
04043         Op1 = Builder->CreateAnd(Op1, Z);
04044         I.setOperand(0, Op1);
04045         I.setOperand(1, Constant::getNullValue(Op1->getType()));
04046         return &I;
04047       }
04048     }
04049 
04050     // Transform (zext A) == (B & (1<<X)-1) --> A == (trunc B)
04051     // and       (B & (1<<X)-1) == (zext A) --> A == (trunc B)
04052     ConstantInt *Cst1;
04053     if ((Op0->hasOneUse() &&
04054          match(Op0, m_ZExt(m_Value(A))) &&
04055          match(Op1, m_And(m_Value(B), m_ConstantInt(Cst1)))) ||
04056         (Op1->hasOneUse() &&
04057          match(Op0, m_And(m_Value(B), m_ConstantInt(Cst1))) &&
04058          match(Op1, m_ZExt(m_Value(A))))) {
04059       APInt Pow2 = Cst1->getValue() + 1;
04060       if (Pow2.isPowerOf2() && isa<IntegerType>(A->getType()) &&
04061           Pow2.logBase2() == cast<IntegerType>(A->getType())->getBitWidth())
04062         return new ICmpInst(I.getPredicate(), A,
04063                             Builder->CreateTrunc(B, A->getType()));
04064     }
04065 
04066     // (A >> C) == (B >> C) --> (A^B) u< (1 << C)
04067     // For lshr and ashr pairs.
04068     if ((match(Op0, m_OneUse(m_LShr(m_Value(A), m_ConstantInt(Cst1)))) &&
04069          match(Op1, m_OneUse(m_LShr(m_Value(B), m_Specific(Cst1))))) ||
04070         (match(Op0, m_OneUse(m_AShr(m_Value(A), m_ConstantInt(Cst1)))) &&
04071          match(Op1, m_OneUse(m_AShr(m_Value(B), m_Specific(Cst1)))))) {
04072       unsigned TypeBits = Cst1->getBitWidth();
04073       unsigned ShAmt = (unsigned)Cst1->getLimitedValue(TypeBits);
04074       if (ShAmt < TypeBits && ShAmt != 0) {
04075         ICmpInst::Predicate Pred = I.getPredicate() == ICmpInst::ICMP_NE
04076                                        ? ICmpInst::ICMP_UGE
04077                                        : ICmpInst::ICMP_ULT;
04078         Value *Xor = Builder->CreateXor(A, B, I.getName() + ".unshifted");
04079         APInt CmpVal = APInt::getOneBitSet(TypeBits, ShAmt);
04080         return new ICmpInst(Pred, Xor, Builder->getInt(CmpVal));
04081       }
04082     }
04083 
04084     // (A << C) == (B << C) --> ((A^B) & (~0U >> C)) == 0
04085     if (match(Op0, m_OneUse(m_Shl(m_Value(A), m_ConstantInt(Cst1)))) &&
04086         match(Op1, m_OneUse(m_Shl(m_Value(B), m_Specific(Cst1))))) {
04087       unsigned TypeBits = Cst1->getBitWidth();
04088       unsigned ShAmt = (unsigned)Cst1->getLimitedValue(TypeBits);
04089       if (ShAmt < TypeBits && ShAmt != 0) {
04090         Value *Xor = Builder->CreateXor(A, B, I.getName() + ".unshifted");
04091         APInt AndVal = APInt::getLowBitsSet(TypeBits, TypeBits - ShAmt);
04092         Value *And = Builder->CreateAnd(Xor, Builder->getInt(AndVal),
04093                                         I.getName() + ".mask");
04094         return new ICmpInst(I.getPredicate(), And,
04095                             Constant::getNullValue(Cst1->getType()));
04096       }
04097     }
04098 
04099     // Transform "icmp eq (trunc (lshr(X, cst1)), cst" to
04100     // "icmp (and X, mask), cst"
04101     uint64_t ShAmt = 0;
04102     if (Op0->hasOneUse() &&
04103         match(Op0, m_Trunc(m_OneUse(m_LShr(m_Value(A),
04104                                            m_ConstantInt(ShAmt))))) &&
04105         match(Op1, m_ConstantInt(Cst1)) &&
04106         // Only do this when A has multiple uses.  This is most important to do
04107         // when it exposes other optimizations.
04108         !A->hasOneUse()) {
04109       unsigned ASize =cast<IntegerType>(A->getType())->getPrimitiveSizeInBits();
04110 
04111       if (ShAmt < ASize) {
04112         APInt MaskV =
04113           APInt::getLowBitsSet(ASize, Op0->getType()->getPrimitiveSizeInBits());
04114         MaskV <<= ShAmt;
04115 
04116         APInt CmpV = Cst1->getValue().zext(ASize);
04117         CmpV <<= ShAmt;
04118 
04119         Value *Mask = Builder->CreateAnd(A, Builder->getInt(MaskV));
04120         return new ICmpInst(I.getPredicate(), Mask, Builder->getInt(CmpV));
04121       }
04122     }
04123   }
04124 
04125   // The 'cmpxchg' instruction returns an aggregate containing the old value and
04126   // an i1 which indicates whether or not we successfully did the swap.
04127   //
04128   // Replace comparisons between the old value and the expected value with the
04129   // indicator that 'cmpxchg' returns.
04130   //
04131   // N.B.  This transform is only valid when the 'cmpxchg' is not permitted to
04132   // spuriously fail.  In those cases, the old value may equal the expected
04133   // value but it is possible for the swap to not occur.
04134   if (I.getPredicate() == ICmpInst::ICMP_EQ)
04135     if (auto *EVI = dyn_cast<ExtractValueInst>(Op0))
04136       if (auto *ACXI = dyn_cast<AtomicCmpXchgInst>(EVI->getAggregateOperand()))
04137         if (EVI->getIndices()[0] == 0 && ACXI->getCompareOperand() == Op1 &&
04138             !ACXI->isWeak())
04139           return ExtractValueInst::Create(ACXI, 1);
04140 
04141   {
04142     Value *X; ConstantInt *Cst;
04143     // icmp X+Cst, X
04144     if (match(Op0, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op1 == X)
04145       return FoldICmpAddOpCst(I, X, Cst, I.getPredicate());
04146 
04147     // icmp X, X+Cst
04148     if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X)
04149       return FoldICmpAddOpCst(I, X, Cst, I.getSwappedPredicate());
04150   }
04151   return Changed ? &I : nullptr;
04152 }
04153 
04154 /// FoldFCmp_IntToFP_Cst - Fold fcmp ([us]itofp x, cst) if possible.
04155 Instruction *InstCombiner::FoldFCmp_IntToFP_Cst(FCmpInst &I,
04156                                                 Instruction *LHSI,
04157                                                 Constant *RHSC) {
04158   if (!isa<ConstantFP>(RHSC)) return nullptr;
04159   const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF();
04160 
04161   // Get the width of the mantissa.  We don't want to hack on conversions that
04162   // might lose information from the integer, e.g. "i64 -> float"
04163   int MantissaWidth = LHSI->getType()->getFPMantissaWidth();
04164   if (MantissaWidth == -1) return nullptr;  // Unknown.
04165 
04166   IntegerType *IntTy = cast<IntegerType>(LHSI->getOperand(0)->getType());
04167 
04168   bool LHSUnsigned = isa<UIToFPInst>(LHSI);
04169 
04170   if (I.isEquality()) {
04171     FCmpInst::Predicate P = I.getPredicate();
04172     bool IsExact = false;
04173     APSInt RHSCvt(IntTy->getBitWidth(), LHSUnsigned);
04174     RHS.convertToInteger(RHSCvt, APFloat::rmNearestTiesToEven, &IsExact);
04175 
04176     // If the floating point constant isn't an integer value, we know if we will
04177     // ever compare equal / not equal to it.
04178     if (!IsExact) {
04179       // TODO: Can never be -0.0 and other non-representable values
04180       APFloat RHSRoundInt(RHS);
04181       RHSRoundInt.roundToIntegral(APFloat::rmNearestTiesToEven);
04182       if (RHS.compare(RHSRoundInt) != APFloat::cmpEqual) {
04183         if (P == FCmpInst::FCMP_OEQ || P == FCmpInst::FCMP_UEQ)
04184           return ReplaceInstUsesWith(I, Builder->getFalse());
04185 
04186         assert(P == FCmpInst::FCMP_ONE || P == FCmpInst::FCMP_UNE);
04187         return ReplaceInstUsesWith(I, Builder->getTrue());
04188       }
04189     }
04190 
04191     // TODO: If the constant is exactly representable, is it always OK to do
04192     // equality compares as integer?
04193   }
04194 
04195   // Check to see that the input is converted from an integer type that is small
04196   // enough that preserves all bits.  TODO: check here for "known" sign bits.
04197   // This would allow us to handle (fptosi (x >>s 62) to float) if x is i64 f.e.
04198   unsigned InputSize = IntTy->getScalarSizeInBits();
04199 
04200   // Following test does NOT adjust InputSize downwards for signed inputs, 
04201   // because the most negative value still requires all the mantissa bits 
04202   // to distinguish it from one less than that value.
04203   if ((int)InputSize > MantissaWidth) {
04204     // Conversion would lose accuracy. Check if loss can impact comparison.
04205     int Exp = ilogb(RHS);
04206     if (Exp == APFloat::IEK_Inf) {
04207       int MaxExponent = ilogb(APFloat::getLargest(RHS.getSemantics()));
04208       if (MaxExponent < (int)InputSize - !LHSUnsigned) 
04209         // Conversion could create infinity.
04210         return nullptr;
04211     } else {
04212       // Note that if RHS is zero or NaN, then Exp is negative 
04213       // and first condition is trivially false.
04214       if (MantissaWidth <= Exp && Exp <= (int)InputSize - !LHSUnsigned) 
04215         // Conversion could affect comparison.
04216         return nullptr;
04217     }
04218   }
04219 
04220   // Otherwise, we can potentially simplify the comparison.  We know that it
04221   // will always come through as an integer value and we know the constant is
04222   // not a NAN (it would have been previously simplified).
04223   assert(!RHS.isNaN() && "NaN comparison not already folded!");
04224 
04225   ICmpInst::Predicate Pred;
04226   switch (I.getPredicate()) {
04227   default: llvm_unreachable("Unexpected predicate!");
04228   case FCmpInst::FCMP_UEQ:
04229   case FCmpInst::FCMP_OEQ:
04230     Pred = ICmpInst::ICMP_EQ;
04231     break;
04232   case FCmpInst::FCMP_UGT:
04233   case FCmpInst::FCMP_OGT:
04234     Pred = LHSUnsigned ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_SGT;
04235     break;
04236   case FCmpInst::FCMP_UGE:
04237   case FCmpInst::FCMP_OGE:
04238     Pred = LHSUnsigned ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_SGE;
04239     break;
04240   case FCmpInst::FCMP_ULT:
04241   case FCmpInst::FCMP_OLT:
04242     Pred = LHSUnsigned ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_SLT;
04243     break;
04244   case FCmpInst::FCMP_ULE:
04245   case FCmpInst::FCMP_OLE:
04246     Pred = LHSUnsigned ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_SLE;
04247     break;
04248   case FCmpInst::FCMP_UNE:
04249   case FCmpInst::FCMP_ONE:
04250     Pred = ICmpInst::ICMP_NE;
04251     break;
04252   case FCmpInst::FCMP_ORD:
04253     return ReplaceInstUsesWith(I, Builder->getTrue());
04254   case FCmpInst::FCMP_UNO:
04255     return ReplaceInstUsesWith(I, Builder->getFalse());
04256   }
04257 
04258   // Now we know that the APFloat is a normal number, zero or inf.
04259 
04260   // See if the FP constant is too large for the integer.  For example,
04261   // comparing an i8 to 300.0.
04262   unsigned IntWidth = IntTy->getScalarSizeInBits();
04263 
04264   if (!LHSUnsigned) {
04265     // If the RHS value is > SignedMax, fold the comparison.  This handles +INF
04266     // and large values.
04267     APFloat SMax(RHS.getSemantics());
04268     SMax.convertFromAPInt(APInt::getSignedMaxValue(IntWidth), true,
04269                           APFloat::rmNearestTiesToEven);
04270     if (SMax.compare(RHS) == APFloat::cmpLessThan) {  // smax < 13123.0
04271       if (Pred == ICmpInst::ICMP_NE  || Pred == ICmpInst::ICMP_SLT ||
04272           Pred == ICmpInst::ICMP_SLE)
04273         return ReplaceInstUsesWith(I, Builder->getTrue());
04274       return ReplaceInstUsesWith(I, Builder->getFalse());
04275     }
04276   } else {
04277     // If the RHS value is > UnsignedMax, fold the comparison. This handles
04278     // +INF and large values.
04279     APFloat UMax(RHS.getSemantics());
04280     UMax.convertFromAPInt(APInt::getMaxValue(IntWidth), false,
04281                           APFloat::rmNearestTiesToEven);
04282     if (UMax.compare(RHS) == APFloat::cmpLessThan) {  // umax < 13123.0
04283       if (Pred == ICmpInst::ICMP_NE  || Pred == ICmpInst::ICMP_ULT ||
04284           Pred == ICmpInst::ICMP_ULE)
04285         return ReplaceInstUsesWith(I, Builder->getTrue());
04286       return ReplaceInstUsesWith(I, Builder->getFalse());
04287     }
04288   }
04289 
04290   if (!LHSUnsigned) {
04291     // See if the RHS value is < SignedMin.
04292     APFloat SMin(RHS.getSemantics());
04293     SMin.convertFromAPInt(APInt::getSignedMinValue(IntWidth), true,
04294                           APFloat::rmNearestTiesToEven);
04295     if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // smin > 12312.0
04296       if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT ||
04297           Pred == ICmpInst::ICMP_SGE)
04298         return ReplaceInstUsesWith(I, Builder->getTrue());
04299       return ReplaceInstUsesWith(I, Builder->getFalse());
04300     }
04301   } else {
04302     // See if the RHS value is < UnsignedMin.
04303     APFloat SMin(RHS.getSemantics());
04304     SMin.convertFromAPInt(APInt::getMinValue(IntWidth), true,
04305                           APFloat::rmNearestTiesToEven);
04306     if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // umin > 12312.0
04307       if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_UGT ||
04308           Pred == ICmpInst::ICMP_UGE)
04309         return ReplaceInstUsesWith(I, Builder->getTrue());
04310       return ReplaceInstUsesWith(I, Builder->getFalse());
04311     }
04312   }
04313 
04314   // Okay, now we know that the FP constant fits in the range [SMIN, SMAX] or
04315   // [0, UMAX], but it may still be fractional.  See if it is fractional by
04316   // casting the FP value to the integer value and back, checking for equality.
04317   // Don't do this for zero, because -0.0 is not fractional.
04318   Constant *RHSInt = LHSUnsigned
04319     ? ConstantExpr::getFPToUI(RHSC, IntTy)
04320     : ConstantExpr::getFPToSI(RHSC, IntTy);
04321   if (!RHS.isZero()) {
04322     bool Equal = LHSUnsigned
04323       ? ConstantExpr::getUIToFP(RHSInt, RHSC->getType()) == RHSC
04324       : ConstantExpr::getSIToFP(RHSInt, RHSC->getType()) == RHSC;
04325     if (!Equal) {
04326       // If we had a comparison against a fractional value, we have to adjust
04327       // the compare predicate and sometimes the value.  RHSC is rounded towards
04328       // zero at this point.
04329       switch (Pred) {
04330       default: llvm_unreachable("Unexpected integer comparison!");
04331       case ICmpInst::ICMP_NE:  // (float)int != 4.4   --> true
04332         return ReplaceInstUsesWith(I, Builder->getTrue());
04333       case ICmpInst::ICMP_EQ:  // (float)int == 4.4   --> false
04334         return ReplaceInstUsesWith(I, Builder->getFalse());
04335       case ICmpInst::ICMP_ULE:
04336         // (float)int <= 4.4   --> int <= 4
04337         // (float)int <= -4.4  --> false
04338         if (RHS.isNegative())
04339           return ReplaceInstUsesWith(I, Builder->getFalse());
04340         break;
04341       case ICmpInst::ICMP_SLE:
04342         // (float)int <= 4.4   --> int <= 4
04343         // (float)int <= -4.4  --> int < -4
04344         if (RHS.isNegative())
04345           Pred = ICmpInst::ICMP_SLT;
04346         break;
04347       case ICmpInst::ICMP_ULT:
04348         // (float)int < -4.4   --> false
04349         // (float)int < 4.4    --> int <= 4
04350         if (RHS.isNegative())
04351           return ReplaceInstUsesWith(I, Builder->getFalse());
04352         Pred = ICmpInst::ICMP_ULE;
04353         break;
04354       case ICmpInst::ICMP_SLT:
04355         // (float)int < -4.4   --> int < -4
04356         // (float)int < 4.4    --> int <= 4
04357         if (!RHS.isNegative())
04358           Pred = ICmpInst::ICMP_SLE;
04359         break;
04360       case ICmpInst::ICMP_UGT:
04361         // (float)int > 4.4    --> int > 4
04362         // (float)int > -4.4   --> true
04363         if (RHS.isNegative())
04364           return ReplaceInstUsesWith(I, Builder->getTrue());
04365         break;
04366       case ICmpInst::ICMP_SGT:
04367         // (float)int > 4.4    --> int > 4
04368         // (float)int > -4.4   --> int >= -4
04369         if (RHS.isNegative())
04370           Pred = ICmpInst::ICMP_SGE;
04371         break;
04372       case ICmpInst::ICMP_UGE:
04373         // (float)int >= -4.4   --> true
04374         // (float)int >= 4.4    --> int > 4
04375         if (RHS.isNegative())
04376           return ReplaceInstUsesWith(I, Builder->getTrue());
04377         Pred = ICmpInst::ICMP_UGT;
04378         break;
04379       case ICmpInst::ICMP_SGE:
04380         // (float)int >= -4.4   --> int >= -4
04381         // (float)int >= 4.4    --> int > 4
04382         if (!RHS.isNegative())
04383           Pred = ICmpInst::ICMP_SGT;
04384         break;
04385       }
04386     }
04387   }
04388 
04389   // Lower this FP comparison into an appropriate integer version of the
04390   // comparison.
04391   return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt);
04392 }
04393 
04394 Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {
04395   bool Changed = false;
04396 
04397   /// Orders the operands of the compare so that they are listed from most
04398   /// complex to least complex.  This puts constants before unary operators,
04399   /// before binary operators.
04400   if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) {
04401     I.swapOperands();
04402     Changed = true;
04403   }
04404 
04405   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
04406 
04407   if (Value *V = SimplifyFCmpInst(I.getPredicate(), Op0, Op1,
04408                                   I.getFastMathFlags(), DL, TLI, DT, AC, &I))
04409     return ReplaceInstUsesWith(I, V);
04410 
04411   // Simplify 'fcmp pred X, X'
04412   if (Op0 == Op1) {
04413     switch (I.getPredicate()) {
04414     default: llvm_unreachable("Unknown predicate!");
04415     case FCmpInst::FCMP_UNO:    // True if unordered: isnan(X) | isnan(Y)
04416     case FCmpInst::FCMP_ULT:    // True if unordered or less than
04417     case FCmpInst::FCMP_UGT:    // True if unordered or greater than
04418     case FCmpInst::FCMP_UNE:    // True if unordered or not equal
04419       // Canonicalize these to be 'fcmp uno %X, 0.0'.
04420       I.setPredicate(FCmpInst::FCMP_UNO);
04421       I.setOperand(1, Constant::getNullValue(Op0->getType()));
04422       return &I;
04423 
04424     case FCmpInst::FCMP_ORD:    // True if ordered (no nans)
04425     case FCmpInst::FCMP_OEQ:    // True if ordered and equal
04426     case FCmpInst::FCMP_OGE:    // True if ordered and greater than or equal
04427     case FCmpInst::FCMP_OLE:    // True if ordered and less than or equal
04428       // Canonicalize these to be 'fcmp ord %X, 0.0'.
04429       I.setPredicate(FCmpInst::FCMP_ORD);
04430       I.setOperand(1, Constant::getNullValue(Op0->getType()));
04431       return &I;
04432     }
04433   }
04434 
04435   // Test if the FCmpInst instruction is used exclusively by a select as
04436   // part of a minimum or maximum operation. If so, refrain from doing
04437   // any other folding. This helps out other analyses which understand
04438   // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
04439   // and CodeGen. And in this case, at least one of the comparison
04440   // operands has at least one user besides the compare (the select),
04441   // which would often largely negate the benefit of folding anyway.
04442   if (I.hasOneUse())
04443     if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin()))
04444       if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
04445           (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
04446         return nullptr;
04447 
04448   // Handle fcmp with constant RHS
04449   if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
04450     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
04451       switch (LHSI->getOpcode()) {
04452       case Instruction::FPExt: {
04453         // fcmp (fpext x), C -> fcmp x, (fptrunc C) if fptrunc is lossless
04454         FPExtInst *LHSExt = cast<FPExtInst>(LHSI);
04455         ConstantFP *RHSF = dyn_cast<ConstantFP>(RHSC);
04456         if (!RHSF)
04457           break;
04458 
04459         const fltSemantics *Sem;
04460         // FIXME: This shouldn't be here.
04461         if (LHSExt->getSrcTy()->isHalfTy())
04462           Sem = &APFloat::IEEEhalf;
04463         else if (LHSExt->getSrcTy()->isFloatTy())
04464           Sem = &APFloat::IEEEsingle;
04465         else if (LHSExt->getSrcTy()->isDoubleTy())
04466           Sem = &APFloat::IEEEdouble;
04467         else if (LHSExt->getSrcTy()->isFP128Ty())
04468           Sem = &APFloat::IEEEquad;
04469         else if (LHSExt->getSrcTy()->isX86_FP80Ty())
04470           Sem = &APFloat::x87DoubleExtended;
04471         else if (LHSExt->getSrcTy()->isPPC_FP128Ty())
04472           Sem = &APFloat::PPCDoubleDouble;
04473         else
04474           break;
04475 
04476         bool Lossy;
04477         APFloat F = RHSF->getValueAPF();
04478         F.convert(*Sem, APFloat::rmNearestTiesToEven, &Lossy);
04479 
04480         // Avoid lossy conversions and denormals. Zero is a special case
04481         // that's OK to convert.
04482         APFloat Fabs = F;
04483         Fabs.clearSign();
04484         if (!Lossy &&
04485             ((Fabs.compare(APFloat::getSmallestNormalized(*Sem)) !=
04486                  APFloat::cmpLessThan) || Fabs.isZero()))
04487 
04488           return new FCmpInst(I.getPredicate(), LHSExt->getOperand(0),
04489                               ConstantFP::get(RHSC->getContext(), F));
04490         break;
04491       }
04492       case Instruction::PHI:
04493         // Only fold fcmp into the PHI if the phi and fcmp are in the same
04494         // block.  If in the same block, we're encouraging jump threading.  If
04495         // not, we are just pessimizing the code by making an i1 phi.
04496         if (LHSI->getParent() == I.getParent())
04497           if (Instruction *NV = FoldOpIntoPhi(I))
04498             return NV;
04499         break;
04500       case Instruction::SIToFP:
04501       case Instruction::UIToFP:
04502         if (Instruction *NV = FoldFCmp_IntToFP_Cst(I, LHSI, RHSC))
04503           return NV;
04504         break;
04505       case Instruction::FSub: {
04506         // fcmp pred (fneg x), C -> fcmp swap(pred) x, -C
04507         Value *Op;
04508         if (match(LHSI, m_FNeg(m_Value(Op))))
04509           return new FCmpInst(I.getSwappedPredicate(), Op,
04510                               ConstantExpr::getFNeg(RHSC));
04511         break;
04512       }
04513       case Instruction::Load:
04514         if (GetElementPtrInst *GEP =
04515             dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
04516           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
04517             if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
04518                 !cast<LoadInst>(LHSI)->isVolatile())
04519               if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
04520                 return Res;
04521         }
04522         break;
04523       case Instruction::Call: {
04524         if (!RHSC->isNullValue())
04525           break;
04526 
04527         CallInst *CI = cast<CallInst>(LHSI);
04528         const Function *F = CI->getCalledFunction();
04529         if (!F)
04530           break;
04531 
04532         // Various optimization for fabs compared with zero.
04533         LibFunc::Func Func;
04534         if (F->getIntrinsicID() == Intrinsic::fabs ||
04535             (TLI->getLibFunc(F->getName(), Func) && TLI->has(Func) &&
04536              (Func == LibFunc::fabs || Func == LibFunc::fabsf ||
04537               Func == LibFunc::fabsl))) {
04538           switch (I.getPredicate()) {
04539           default:
04540             break;
04541             // fabs(x) < 0 --> false
04542           case FCmpInst::FCMP_OLT:
04543             return ReplaceInstUsesWith(I, Builder->getFalse());
04544             // fabs(x) > 0 --> x != 0
04545           case FCmpInst::FCMP_OGT:
04546             return new FCmpInst(FCmpInst::FCMP_ONE, CI->getArgOperand(0), RHSC);
04547             // fabs(x) <= 0 --> x == 0
04548           case FCmpInst::FCMP_OLE:
04549             return new FCmpInst(FCmpInst::FCMP_OEQ, CI->getArgOperand(0), RHSC);
04550             // fabs(x) >= 0 --> !isnan(x)
04551           case FCmpInst::FCMP_OGE:
04552             return new FCmpInst(FCmpInst::FCMP_ORD, CI->getArgOperand(0), RHSC);
04553             // fabs(x) == 0 --> x == 0
04554             // fabs(x) != 0 --> x != 0
04555           case FCmpInst::FCMP_OEQ:
04556           case FCmpInst::FCMP_UEQ:
04557           case FCmpInst::FCMP_ONE:
04558           case FCmpInst::FCMP_UNE:
04559             return new FCmpInst(I.getPredicate(), CI->getArgOperand(0), RHSC);
04560           }
04561         }
04562       }
04563       }
04564   }
04565 
04566   // fcmp pred (fneg x), (fneg y) -> fcmp swap(pred) x, y
04567   Value *X, *Y;
04568   if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
04569     return new FCmpInst(I.getSwappedPredicate(), X, Y);
04570 
04571   // fcmp (fpext x), (fpext y) -> fcmp x, y
04572   if (FPExtInst *LHSExt = dyn_cast<FPExtInst>(Op0))
04573     if (FPExtInst *RHSExt = dyn_cast<FPExtInst>(Op1))
04574       if (LHSExt->getSrcTy() == RHSExt->getSrcTy())
04575         return new FCmpInst(I.getPredicate(), LHSExt->getOperand(0),
04576                             RHSExt->getOperand(0));
04577 
04578   return Changed ? &I : nullptr;
04579 }