LLVM API Documentation

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