LLVM  mainline
InstructionSimplify.cpp
Go to the documentation of this file.
00001 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
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 routines for folding instructions into simpler forms
00011 // that do not require creating new instructions.  This does constant folding
00012 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
00013 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
00014 // ("and i32 %x, %x" -> "%x").  All operands are assumed to have already been
00015 // simplified: This is usually true and assuming it simplifies the logic (if
00016 // they have not been simplified then results are correct but maybe suboptimal).
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #include "llvm/Analysis/InstructionSimplify.h"
00021 #include "llvm/ADT/SetVector.h"
00022 #include "llvm/ADT/Statistic.h"
00023 #include "llvm/Analysis/AliasAnalysis.h"
00024 #include "llvm/Analysis/ConstantFolding.h"
00025 #include "llvm/Analysis/MemoryBuiltins.h"
00026 #include "llvm/Analysis/ValueTracking.h"
00027 #include "llvm/IR/ConstantRange.h"
00028 #include "llvm/IR/DataLayout.h"
00029 #include "llvm/IR/Dominators.h"
00030 #include "llvm/IR/GetElementPtrTypeIterator.h"
00031 #include "llvm/IR/GlobalAlias.h"
00032 #include "llvm/IR/Operator.h"
00033 #include "llvm/IR/PatternMatch.h"
00034 #include "llvm/IR/ValueHandle.h"
00035 #include <algorithm>
00036 using namespace llvm;
00037 using namespace llvm::PatternMatch;
00038 
00039 #define DEBUG_TYPE "instsimplify"
00040 
00041 enum { RecursionLimit = 3 };
00042 
00043 STATISTIC(NumExpand,  "Number of expansions");
00044 STATISTIC(NumReassoc, "Number of reassociations");
00045 
00046 namespace {
00047 struct Query {
00048   const DataLayout &DL;
00049   const TargetLibraryInfo *TLI;
00050   const DominatorTree *DT;
00051   AssumptionCache *AC;
00052   const Instruction *CxtI;
00053 
00054   Query(const DataLayout &DL, const TargetLibraryInfo *tli,
00055         const DominatorTree *dt, AssumptionCache *ac = nullptr,
00056         const Instruction *cxti = nullptr)
00057       : DL(DL), TLI(tli), DT(dt), AC(ac), CxtI(cxti) {}
00058 };
00059 } // end anonymous namespace
00060 
00061 static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned);
00062 static Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &,
00063                             unsigned);
00064 static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &,
00065                               const Query &, unsigned);
00066 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &,
00067                               unsigned);
00068 static Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned);
00069 static Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned);
00070 static Value *SimplifyTruncInst(Value *, Type *, const Query &, unsigned);
00071 
00072 /// getFalse - For a boolean type, or a vector of boolean type, return false, or
00073 /// a vector with every element false, as appropriate for the type.
00074 static Constant *getFalse(Type *Ty) {
00075   assert(Ty->getScalarType()->isIntegerTy(1) &&
00076          "Expected i1 type or a vector of i1!");
00077   return Constant::getNullValue(Ty);
00078 }
00079 
00080 /// getTrue - For a boolean type, or a vector of boolean type, return true, or
00081 /// a vector with every element true, as appropriate for the type.
00082 static Constant *getTrue(Type *Ty) {
00083   assert(Ty->getScalarType()->isIntegerTy(1) &&
00084          "Expected i1 type or a vector of i1!");
00085   return Constant::getAllOnesValue(Ty);
00086 }
00087 
00088 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
00089 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
00090                           Value *RHS) {
00091   CmpInst *Cmp = dyn_cast<CmpInst>(V);
00092   if (!Cmp)
00093     return false;
00094   CmpInst::Predicate CPred = Cmp->getPredicate();
00095   Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
00096   if (CPred == Pred && CLHS == LHS && CRHS == RHS)
00097     return true;
00098   return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
00099     CRHS == LHS;
00100 }
00101 
00102 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
00103 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
00104   Instruction *I = dyn_cast<Instruction>(V);
00105   if (!I)
00106     // Arguments and constants dominate all instructions.
00107     return true;
00108 
00109   // If we are processing instructions (and/or basic blocks) that have not been
00110   // fully added to a function, the parent nodes may still be null. Simply
00111   // return the conservative answer in these cases.
00112   if (!I->getParent() || !P->getParent() || !I->getParent()->getParent())
00113     return false;
00114 
00115   // If we have a DominatorTree then do a precise test.
00116   if (DT) {
00117     if (!DT->isReachableFromEntry(P->getParent()))
00118       return true;
00119     if (!DT->isReachableFromEntry(I->getParent()))
00120       return false;
00121     return DT->dominates(I, P);
00122   }
00123 
00124   // Otherwise, if the instruction is in the entry block, and is not an invoke,
00125   // then it obviously dominates all phi nodes.
00126   if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
00127       !isa<InvokeInst>(I))
00128     return true;
00129 
00130   return false;
00131 }
00132 
00133 /// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning
00134 /// it into "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
00135 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
00136 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
00137 /// Returns the simplified value, or null if no simplification was performed.
00138 static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS,
00139                           unsigned OpcToExpand, const Query &Q,
00140                           unsigned MaxRecurse) {
00141   Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand;
00142   // Recursion is always used, so bail out at once if we already hit the limit.
00143   if (!MaxRecurse--)
00144     return nullptr;
00145 
00146   // Check whether the expression has the form "(A op' B) op C".
00147   if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
00148     if (Op0->getOpcode() == OpcodeToExpand) {
00149       // It does!  Try turning it into "(A op C) op' (B op C)".
00150       Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
00151       // Do "A op C" and "B op C" both simplify?
00152       if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
00153         if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
00154           // They do! Return "L op' R" if it simplifies or is already available.
00155           // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
00156           if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
00157                                      && L == B && R == A)) {
00158             ++NumExpand;
00159             return LHS;
00160           }
00161           // Otherwise return "L op' R" if it simplifies.
00162           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
00163             ++NumExpand;
00164             return V;
00165           }
00166         }
00167     }
00168 
00169   // Check whether the expression has the form "A op (B op' C)".
00170   if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
00171     if (Op1->getOpcode() == OpcodeToExpand) {
00172       // It does!  Try turning it into "(A op B) op' (A op C)".
00173       Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
00174       // Do "A op B" and "A op C" both simplify?
00175       if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
00176         if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
00177           // They do! Return "L op' R" if it simplifies or is already available.
00178           // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
00179           if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
00180                                      && L == C && R == B)) {
00181             ++NumExpand;
00182             return RHS;
00183           }
00184           // Otherwise return "L op' R" if it simplifies.
00185           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
00186             ++NumExpand;
00187             return V;
00188           }
00189         }
00190     }
00191 
00192   return nullptr;
00193 }
00194 
00195 /// SimplifyAssociativeBinOp - Generic simplifications for associative binary
00196 /// operations.  Returns the simpler value, or null if none was found.
00197 static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS,
00198                                        const Query &Q, unsigned MaxRecurse) {
00199   Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc;
00200   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
00201 
00202   // Recursion is always used, so bail out at once if we already hit the limit.
00203   if (!MaxRecurse--)
00204     return nullptr;
00205 
00206   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
00207   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
00208 
00209   // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
00210   if (Op0 && Op0->getOpcode() == Opcode) {
00211     Value *A = Op0->getOperand(0);
00212     Value *B = Op0->getOperand(1);
00213     Value *C = RHS;
00214 
00215     // Does "B op C" simplify?
00216     if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
00217       // It does!  Return "A op V" if it simplifies or is already available.
00218       // If V equals B then "A op V" is just the LHS.
00219       if (V == B) return LHS;
00220       // Otherwise return "A op V" if it simplifies.
00221       if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
00222         ++NumReassoc;
00223         return W;
00224       }
00225     }
00226   }
00227 
00228   // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
00229   if (Op1 && Op1->getOpcode() == Opcode) {
00230     Value *A = LHS;
00231     Value *B = Op1->getOperand(0);
00232     Value *C = Op1->getOperand(1);
00233 
00234     // Does "A op B" simplify?
00235     if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
00236       // It does!  Return "V op C" if it simplifies or is already available.
00237       // If V equals B then "V op C" is just the RHS.
00238       if (V == B) return RHS;
00239       // Otherwise return "V op C" if it simplifies.
00240       if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
00241         ++NumReassoc;
00242         return W;
00243       }
00244     }
00245   }
00246 
00247   // The remaining transforms require commutativity as well as associativity.
00248   if (!Instruction::isCommutative(Opcode))
00249     return nullptr;
00250 
00251   // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
00252   if (Op0 && Op0->getOpcode() == Opcode) {
00253     Value *A = Op0->getOperand(0);
00254     Value *B = Op0->getOperand(1);
00255     Value *C = RHS;
00256 
00257     // Does "C op A" simplify?
00258     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
00259       // It does!  Return "V op B" if it simplifies or is already available.
00260       // If V equals A then "V op B" is just the LHS.
00261       if (V == A) return LHS;
00262       // Otherwise return "V op B" if it simplifies.
00263       if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
00264         ++NumReassoc;
00265         return W;
00266       }
00267     }
00268   }
00269 
00270   // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
00271   if (Op1 && Op1->getOpcode() == Opcode) {
00272     Value *A = LHS;
00273     Value *B = Op1->getOperand(0);
00274     Value *C = Op1->getOperand(1);
00275 
00276     // Does "C op A" simplify?
00277     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
00278       // It does!  Return "B op V" if it simplifies or is already available.
00279       // If V equals C then "B op V" is just the RHS.
00280       if (V == C) return RHS;
00281       // Otherwise return "B op V" if it simplifies.
00282       if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
00283         ++NumReassoc;
00284         return W;
00285       }
00286     }
00287   }
00288 
00289   return nullptr;
00290 }
00291 
00292 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
00293 /// instruction as an operand, try to simplify the binop by seeing whether
00294 /// evaluating it on both branches of the select results in the same value.
00295 /// Returns the common value if so, otherwise returns null.
00296 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
00297                                     const Query &Q, unsigned MaxRecurse) {
00298   // Recursion is always used, so bail out at once if we already hit the limit.
00299   if (!MaxRecurse--)
00300     return nullptr;
00301 
00302   SelectInst *SI;
00303   if (isa<SelectInst>(LHS)) {
00304     SI = cast<SelectInst>(LHS);
00305   } else {
00306     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
00307     SI = cast<SelectInst>(RHS);
00308   }
00309 
00310   // Evaluate the BinOp on the true and false branches of the select.
00311   Value *TV;
00312   Value *FV;
00313   if (SI == LHS) {
00314     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
00315     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
00316   } else {
00317     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
00318     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
00319   }
00320 
00321   // If they simplified to the same value, then return the common value.
00322   // If they both failed to simplify then return null.
00323   if (TV == FV)
00324     return TV;
00325 
00326   // If one branch simplified to undef, return the other one.
00327   if (TV && isa<UndefValue>(TV))
00328     return FV;
00329   if (FV && isa<UndefValue>(FV))
00330     return TV;
00331 
00332   // If applying the operation did not change the true and false select values,
00333   // then the result of the binop is the select itself.
00334   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
00335     return SI;
00336 
00337   // If one branch simplified and the other did not, and the simplified
00338   // value is equal to the unsimplified one, return the simplified value.
00339   // For example, select (cond, X, X & Z) & Z -> X & Z.
00340   if ((FV && !TV) || (TV && !FV)) {
00341     // Check that the simplified value has the form "X op Y" where "op" is the
00342     // same as the original operation.
00343     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
00344     if (Simplified && Simplified->getOpcode() == Opcode) {
00345       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
00346       // We already know that "op" is the same as for the simplified value.  See
00347       // if the operands match too.  If so, return the simplified value.
00348       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
00349       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
00350       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
00351       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
00352           Simplified->getOperand(1) == UnsimplifiedRHS)
00353         return Simplified;
00354       if (Simplified->isCommutative() &&
00355           Simplified->getOperand(1) == UnsimplifiedLHS &&
00356           Simplified->getOperand(0) == UnsimplifiedRHS)
00357         return Simplified;
00358     }
00359   }
00360 
00361   return nullptr;
00362 }
00363 
00364 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
00365 /// try to simplify the comparison by seeing whether both branches of the select
00366 /// result in the same value.  Returns the common value if so, otherwise returns
00367 /// null.
00368 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
00369                                   Value *RHS, const Query &Q,
00370                                   unsigned MaxRecurse) {
00371   // Recursion is always used, so bail out at once if we already hit the limit.
00372   if (!MaxRecurse--)
00373     return nullptr;
00374 
00375   // Make sure the select is on the LHS.
00376   if (!isa<SelectInst>(LHS)) {
00377     std::swap(LHS, RHS);
00378     Pred = CmpInst::getSwappedPredicate(Pred);
00379   }
00380   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
00381   SelectInst *SI = cast<SelectInst>(LHS);
00382   Value *Cond = SI->getCondition();
00383   Value *TV = SI->getTrueValue();
00384   Value *FV = SI->getFalseValue();
00385 
00386   // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
00387   // Does "cmp TV, RHS" simplify?
00388   Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse);
00389   if (TCmp == Cond) {
00390     // It not only simplified, it simplified to the select condition.  Replace
00391     // it with 'true'.
00392     TCmp = getTrue(Cond->getType());
00393   } else if (!TCmp) {
00394     // It didn't simplify.  However if "cmp TV, RHS" is equal to the select
00395     // condition then we can replace it with 'true'.  Otherwise give up.
00396     if (!isSameCompare(Cond, Pred, TV, RHS))
00397       return nullptr;
00398     TCmp = getTrue(Cond->getType());
00399   }
00400 
00401   // Does "cmp FV, RHS" simplify?
00402   Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse);
00403   if (FCmp == Cond) {
00404     // It not only simplified, it simplified to the select condition.  Replace
00405     // it with 'false'.
00406     FCmp = getFalse(Cond->getType());
00407   } else if (!FCmp) {
00408     // It didn't simplify.  However if "cmp FV, RHS" is equal to the select
00409     // condition then we can replace it with 'false'.  Otherwise give up.
00410     if (!isSameCompare(Cond, Pred, FV, RHS))
00411       return nullptr;
00412     FCmp = getFalse(Cond->getType());
00413   }
00414 
00415   // If both sides simplified to the same value, then use it as the result of
00416   // the original comparison.
00417   if (TCmp == FCmp)
00418     return TCmp;
00419 
00420   // The remaining cases only make sense if the select condition has the same
00421   // type as the result of the comparison, so bail out if this is not so.
00422   if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
00423     return nullptr;
00424   // If the false value simplified to false, then the result of the compare
00425   // is equal to "Cond && TCmp".  This also catches the case when the false
00426   // value simplified to false and the true value to true, returning "Cond".
00427   if (match(FCmp, m_Zero()))
00428     if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse))
00429       return V;
00430   // If the true value simplified to true, then the result of the compare
00431   // is equal to "Cond || FCmp".
00432   if (match(TCmp, m_One()))
00433     if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse))
00434       return V;
00435   // Finally, if the false value simplified to true and the true value to
00436   // false, then the result of the compare is equal to "!Cond".
00437   if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
00438     if (Value *V =
00439         SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
00440                         Q, MaxRecurse))
00441       return V;
00442 
00443   return nullptr;
00444 }
00445 
00446 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
00447 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
00448 /// it on the incoming phi values yields the same result for every value.  If so
00449 /// returns the common value, otherwise returns null.
00450 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
00451                                  const Query &Q, unsigned MaxRecurse) {
00452   // Recursion is always used, so bail out at once if we already hit the limit.
00453   if (!MaxRecurse--)
00454     return nullptr;
00455 
00456   PHINode *PI;
00457   if (isa<PHINode>(LHS)) {
00458     PI = cast<PHINode>(LHS);
00459     // Bail out if RHS and the phi may be mutually interdependent due to a loop.
00460     if (!ValueDominatesPHI(RHS, PI, Q.DT))
00461       return nullptr;
00462   } else {
00463     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
00464     PI = cast<PHINode>(RHS);
00465     // Bail out if LHS and the phi may be mutually interdependent due to a loop.
00466     if (!ValueDominatesPHI(LHS, PI, Q.DT))
00467       return nullptr;
00468   }
00469 
00470   // Evaluate the BinOp on the incoming phi values.
00471   Value *CommonValue = nullptr;
00472   for (Value *Incoming : PI->incoming_values()) {
00473     // If the incoming value is the phi node itself, it can safely be skipped.
00474     if (Incoming == PI) continue;
00475     Value *V = PI == LHS ?
00476       SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
00477       SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
00478     // If the operation failed to simplify, or simplified to a different value
00479     // to previously, then give up.
00480     if (!V || (CommonValue && V != CommonValue))
00481       return nullptr;
00482     CommonValue = V;
00483   }
00484 
00485   return CommonValue;
00486 }
00487 
00488 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
00489 /// try to simplify the comparison by seeing whether comparing with all of the
00490 /// incoming phi values yields the same result every time.  If so returns the
00491 /// common result, otherwise returns null.
00492 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
00493                                const Query &Q, unsigned MaxRecurse) {
00494   // Recursion is always used, so bail out at once if we already hit the limit.
00495   if (!MaxRecurse--)
00496     return nullptr;
00497 
00498   // Make sure the phi is on the LHS.
00499   if (!isa<PHINode>(LHS)) {
00500     std::swap(LHS, RHS);
00501     Pred = CmpInst::getSwappedPredicate(Pred);
00502   }
00503   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
00504   PHINode *PI = cast<PHINode>(LHS);
00505 
00506   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
00507   if (!ValueDominatesPHI(RHS, PI, Q.DT))
00508     return nullptr;
00509 
00510   // Evaluate the BinOp on the incoming phi values.
00511   Value *CommonValue = nullptr;
00512   for (Value *Incoming : PI->incoming_values()) {
00513     // If the incoming value is the phi node itself, it can safely be skipped.
00514     if (Incoming == PI) continue;
00515     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
00516     // If the operation failed to simplify, or simplified to a different value
00517     // to previously, then give up.
00518     if (!V || (CommonValue && V != CommonValue))
00519       return nullptr;
00520     CommonValue = V;
00521   }
00522 
00523   return CommonValue;
00524 }
00525 
00526 /// SimplifyAddInst - Given operands for an Add, see if we can
00527 /// fold the result.  If not, this returns null.
00528 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00529                               const Query &Q, unsigned MaxRecurse) {
00530   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00531     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00532       Constant *Ops[] = { CLHS, CRHS };
00533       return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), Ops,
00534                                       Q.DL, Q.TLI);
00535     }
00536 
00537     // Canonicalize the constant to the RHS.
00538     std::swap(Op0, Op1);
00539   }
00540 
00541   // X + undef -> undef
00542   if (match(Op1, m_Undef()))
00543     return Op1;
00544 
00545   // X + 0 -> X
00546   if (match(Op1, m_Zero()))
00547     return Op0;
00548 
00549   // X + (Y - X) -> Y
00550   // (Y - X) + X -> Y
00551   // Eg: X + -X -> 0
00552   Value *Y = nullptr;
00553   if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
00554       match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
00555     return Y;
00556 
00557   // X + ~X -> -1   since   ~X = -X-1
00558   if (match(Op0, m_Not(m_Specific(Op1))) ||
00559       match(Op1, m_Not(m_Specific(Op0))))
00560     return Constant::getAllOnesValue(Op0->getType());
00561 
00562   /// i1 add -> xor.
00563   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
00564     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
00565       return V;
00566 
00567   // Try some generic simplifications for associative operations.
00568   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
00569                                           MaxRecurse))
00570     return V;
00571 
00572   // Threading Add over selects and phi nodes is pointless, so don't bother.
00573   // Threading over the select in "A + select(cond, B, C)" means evaluating
00574   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
00575   // only if B and C are equal.  If B and C are equal then (since we assume
00576   // that operands have already been simplified) "select(cond, B, C)" should
00577   // have been simplified to the common value of B and C already.  Analysing
00578   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
00579   // for threading over phi nodes.
00580 
00581   return nullptr;
00582 }
00583 
00584 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00585                              const DataLayout &DL, const TargetLibraryInfo *TLI,
00586                              const DominatorTree *DT, AssumptionCache *AC,
00587                              const Instruction *CxtI) {
00588   return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI),
00589                            RecursionLimit);
00590 }
00591 
00592 /// \brief Compute the base pointer and cumulative constant offsets for V.
00593 ///
00594 /// This strips all constant offsets off of V, leaving it the base pointer, and
00595 /// accumulates the total constant offset applied in the returned constant. It
00596 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
00597 /// no constant offsets applied.
00598 ///
00599 /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't
00600 /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc.
00601 /// folding.
00602 static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V,
00603                                                 bool AllowNonInbounds = false) {
00604   assert(V->getType()->getScalarType()->isPointerTy());
00605 
00606   Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType();
00607   APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth());
00608 
00609   // Even though we don't look through PHI nodes, we could be called on an
00610   // instruction in an unreachable block, which may be on a cycle.
00611   SmallPtrSet<Value *, 4> Visited;
00612   Visited.insert(V);
00613   do {
00614     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00615       if ((!AllowNonInbounds && !GEP->isInBounds()) ||
00616           !GEP->accumulateConstantOffset(DL, Offset))
00617         break;
00618       V = GEP->getPointerOperand();
00619     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
00620       V = cast<Operator>(V)->getOperand(0);
00621     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
00622       if (GA->mayBeOverridden())
00623         break;
00624       V = GA->getAliasee();
00625     } else {
00626       break;
00627     }
00628     assert(V->getType()->getScalarType()->isPointerTy() &&
00629            "Unexpected operand type!");
00630   } while (Visited.insert(V).second);
00631 
00632   Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset);
00633   if (V->getType()->isVectorTy())
00634     return ConstantVector::getSplat(V->getType()->getVectorNumElements(),
00635                                     OffsetIntPtr);
00636   return OffsetIntPtr;
00637 }
00638 
00639 /// \brief Compute the constant difference between two pointer values.
00640 /// If the difference is not a constant, returns zero.
00641 static Constant *computePointerDifference(const DataLayout &DL, Value *LHS,
00642                                           Value *RHS) {
00643   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
00644   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
00645 
00646   // If LHS and RHS are not related via constant offsets to the same base
00647   // value, there is nothing we can do here.
00648   if (LHS != RHS)
00649     return nullptr;
00650 
00651   // Otherwise, the difference of LHS - RHS can be computed as:
00652   //    LHS - RHS
00653   //  = (LHSOffset + Base) - (RHSOffset + Base)
00654   //  = LHSOffset - RHSOffset
00655   return ConstantExpr::getSub(LHSOffset, RHSOffset);
00656 }
00657 
00658 /// SimplifySubInst - Given operands for a Sub, see if we can
00659 /// fold the result.  If not, this returns null.
00660 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00661                               const Query &Q, unsigned MaxRecurse) {
00662   if (Constant *CLHS = dyn_cast<Constant>(Op0))
00663     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00664       Constant *Ops[] = { CLHS, CRHS };
00665       return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
00666                                       Ops, Q.DL, Q.TLI);
00667     }
00668 
00669   // X - undef -> undef
00670   // undef - X -> undef
00671   if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
00672     return UndefValue::get(Op0->getType());
00673 
00674   // X - 0 -> X
00675   if (match(Op1, m_Zero()))
00676     return Op0;
00677 
00678   // X - X -> 0
00679   if (Op0 == Op1)
00680     return Constant::getNullValue(Op0->getType());
00681 
00682   // 0 - X -> 0 if the sub is NUW.
00683   if (isNUW && match(Op0, m_Zero()))
00684     return Op0;
00685 
00686   // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
00687   // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
00688   Value *X = nullptr, *Y = nullptr, *Z = Op1;
00689   if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
00690     // See if "V === Y - Z" simplifies.
00691     if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
00692       // It does!  Now see if "X + V" simplifies.
00693       if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
00694         // It does, we successfully reassociated!
00695         ++NumReassoc;
00696         return W;
00697       }
00698     // See if "V === X - Z" simplifies.
00699     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
00700       // It does!  Now see if "Y + V" simplifies.
00701       if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) {
00702         // It does, we successfully reassociated!
00703         ++NumReassoc;
00704         return W;
00705       }
00706   }
00707 
00708   // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
00709   // For example, X - (X + 1) -> -1
00710   X = Op0;
00711   if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
00712     // See if "V === X - Y" simplifies.
00713     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
00714       // It does!  Now see if "V - Z" simplifies.
00715       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) {
00716         // It does, we successfully reassociated!
00717         ++NumReassoc;
00718         return W;
00719       }
00720     // See if "V === X - Z" simplifies.
00721     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
00722       // It does!  Now see if "V - Y" simplifies.
00723       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) {
00724         // It does, we successfully reassociated!
00725         ++NumReassoc;
00726         return W;
00727       }
00728   }
00729 
00730   // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
00731   // For example, X - (X - Y) -> Y.
00732   Z = Op0;
00733   if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
00734     // See if "V === Z - X" simplifies.
00735     if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1))
00736       // It does!  Now see if "V + Y" simplifies.
00737       if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) {
00738         // It does, we successfully reassociated!
00739         ++NumReassoc;
00740         return W;
00741       }
00742 
00743   // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
00744   if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
00745       match(Op1, m_Trunc(m_Value(Y))))
00746     if (X->getType() == Y->getType())
00747       // See if "V === X - Y" simplifies.
00748       if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
00749         // It does!  Now see if "trunc V" simplifies.
00750         if (Value *W = SimplifyTruncInst(V, Op0->getType(), Q, MaxRecurse-1))
00751           // It does, return the simplified "trunc V".
00752           return W;
00753 
00754   // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
00755   if (match(Op0, m_PtrToInt(m_Value(X))) &&
00756       match(Op1, m_PtrToInt(m_Value(Y))))
00757     if (Constant *Result = computePointerDifference(Q.DL, X, Y))
00758       return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
00759 
00760   // i1 sub -> xor.
00761   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
00762     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
00763       return V;
00764 
00765   // Threading Sub over selects and phi nodes is pointless, so don't bother.
00766   // Threading over the select in "A - select(cond, B, C)" means evaluating
00767   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
00768   // only if B and C are equal.  If B and C are equal then (since we assume
00769   // that operands have already been simplified) "select(cond, B, C)" should
00770   // have been simplified to the common value of B and C already.  Analysing
00771   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
00772   // for threading over phi nodes.
00773 
00774   return nullptr;
00775 }
00776 
00777 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00778                              const DataLayout &DL, const TargetLibraryInfo *TLI,
00779                              const DominatorTree *DT, AssumptionCache *AC,
00780                              const Instruction *CxtI) {
00781   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI),
00782                            RecursionLimit);
00783 }
00784 
00785 /// Given operands for an FAdd, see if we can fold the result.  If not, this
00786 /// returns null.
00787 static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
00788                               const Query &Q, unsigned MaxRecurse) {
00789   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00790     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00791       Constant *Ops[] = { CLHS, CRHS };
00792       return ConstantFoldInstOperands(Instruction::FAdd, CLHS->getType(),
00793                                       Ops, Q.DL, Q.TLI);
00794     }
00795 
00796     // Canonicalize the constant to the RHS.
00797     std::swap(Op0, Op1);
00798   }
00799 
00800   // fadd X, -0 ==> X
00801   if (match(Op1, m_NegZero()))
00802     return Op0;
00803 
00804   // fadd X, 0 ==> X, when we know X is not -0
00805   if (match(Op1, m_Zero()) &&
00806       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0)))
00807     return Op0;
00808 
00809   // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0
00810   //   where nnan and ninf have to occur at least once somewhere in this
00811   //   expression
00812   Value *SubOp = nullptr;
00813   if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0))))
00814     SubOp = Op1;
00815   else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1))))
00816     SubOp = Op0;
00817   if (SubOp) {
00818     Instruction *FSub = cast<Instruction>(SubOp);
00819     if ((FMF.noNaNs() || FSub->hasNoNaNs()) &&
00820         (FMF.noInfs() || FSub->hasNoInfs()))
00821       return Constant::getNullValue(Op0->getType());
00822   }
00823 
00824   return nullptr;
00825 }
00826 
00827 /// Given operands for an FSub, see if we can fold the result.  If not, this
00828 /// returns null.
00829 static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
00830                               const Query &Q, unsigned MaxRecurse) {
00831   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00832     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00833       Constant *Ops[] = { CLHS, CRHS };
00834       return ConstantFoldInstOperands(Instruction::FSub, CLHS->getType(),
00835                                       Ops, Q.DL, Q.TLI);
00836     }
00837   }
00838 
00839   // fsub X, 0 ==> X
00840   if (match(Op1, m_Zero()))
00841     return Op0;
00842 
00843   // fsub X, -0 ==> X, when we know X is not -0
00844   if (match(Op1, m_NegZero()) &&
00845       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0)))
00846     return Op0;
00847 
00848   // fsub 0, (fsub -0.0, X) ==> X
00849   Value *X;
00850   if (match(Op0, m_AnyZero())) {
00851     if (match(Op1, m_FSub(m_NegZero(), m_Value(X))))
00852       return X;
00853     if (FMF.noSignedZeros() && match(Op1, m_FSub(m_AnyZero(), m_Value(X))))
00854       return X;
00855   }
00856 
00857   // fsub nnan x, x ==> 0.0
00858   if (FMF.noNaNs() && Op0 == Op1)
00859     return Constant::getNullValue(Op0->getType());
00860 
00861   return nullptr;
00862 }
00863 
00864 /// Given the operands for an FMul, see if we can fold the result
00865 static Value *SimplifyFMulInst(Value *Op0, Value *Op1,
00866                                FastMathFlags FMF,
00867                                const Query &Q,
00868                                unsigned MaxRecurse) {
00869  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00870     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00871       Constant *Ops[] = { CLHS, CRHS };
00872       return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(),
00873                                       Ops, Q.DL, Q.TLI);
00874     }
00875 
00876     // Canonicalize the constant to the RHS.
00877     std::swap(Op0, Op1);
00878  }
00879 
00880  // fmul X, 1.0 ==> X
00881  if (match(Op1, m_FPOne()))
00882    return Op0;
00883 
00884  // fmul nnan nsz X, 0 ==> 0
00885  if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero()))
00886    return Op1;
00887 
00888  return nullptr;
00889 }
00890 
00891 /// SimplifyMulInst - Given operands for a Mul, see if we can
00892 /// fold the result.  If not, this returns null.
00893 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q,
00894                               unsigned MaxRecurse) {
00895   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00896     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00897       Constant *Ops[] = { CLHS, CRHS };
00898       return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(),
00899                                       Ops, Q.DL, Q.TLI);
00900     }
00901 
00902     // Canonicalize the constant to the RHS.
00903     std::swap(Op0, Op1);
00904   }
00905 
00906   // X * undef -> 0
00907   if (match(Op1, m_Undef()))
00908     return Constant::getNullValue(Op0->getType());
00909 
00910   // X * 0 -> 0
00911   if (match(Op1, m_Zero()))
00912     return Op1;
00913 
00914   // X * 1 -> X
00915   if (match(Op1, m_One()))
00916     return Op0;
00917 
00918   // (X / Y) * Y -> X if the division is exact.
00919   Value *X = nullptr;
00920   if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
00921       match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0)))))   // Y * (X / Y)
00922     return X;
00923 
00924   // i1 mul -> and.
00925   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
00926     if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1))
00927       return V;
00928 
00929   // Try some generic simplifications for associative operations.
00930   if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q,
00931                                           MaxRecurse))
00932     return V;
00933 
00934   // Mul distributes over Add.  Try some generic simplifications based on this.
00935   if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
00936                              Q, MaxRecurse))
00937     return V;
00938 
00939   // If the operation is with the result of a select instruction, check whether
00940   // operating on either branch of the select always yields the same value.
00941   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
00942     if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q,
00943                                          MaxRecurse))
00944       return V;
00945 
00946   // If the operation is with the result of a phi instruction, check whether
00947   // operating on all incoming values of the phi always yields the same value.
00948   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
00949     if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q,
00950                                       MaxRecurse))
00951       return V;
00952 
00953   return nullptr;
00954 }
00955 
00956 Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
00957                               const DataLayout &DL,
00958                               const TargetLibraryInfo *TLI,
00959                               const DominatorTree *DT, AssumptionCache *AC,
00960                               const Instruction *CxtI) {
00961   return ::SimplifyFAddInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
00962                             RecursionLimit);
00963 }
00964 
00965 Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
00966                               const DataLayout &DL,
00967                               const TargetLibraryInfo *TLI,
00968                               const DominatorTree *DT, AssumptionCache *AC,
00969                               const Instruction *CxtI) {
00970   return ::SimplifyFSubInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
00971                             RecursionLimit);
00972 }
00973 
00974 Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
00975                               const DataLayout &DL,
00976                               const TargetLibraryInfo *TLI,
00977                               const DominatorTree *DT, AssumptionCache *AC,
00978                               const Instruction *CxtI) {
00979   return ::SimplifyFMulInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
00980                             RecursionLimit);
00981 }
00982 
00983 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout &DL,
00984                              const TargetLibraryInfo *TLI,
00985                              const DominatorTree *DT, AssumptionCache *AC,
00986                              const Instruction *CxtI) {
00987   return ::SimplifyMulInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
00988                            RecursionLimit);
00989 }
00990 
00991 /// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can
00992 /// fold the result.  If not, this returns null.
00993 static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
00994                           const Query &Q, unsigned MaxRecurse) {
00995   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
00996     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
00997       Constant *Ops[] = { C0, C1 };
00998       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI);
00999     }
01000   }
01001 
01002   bool isSigned = Opcode == Instruction::SDiv;
01003 
01004   // X / undef -> undef
01005   if (match(Op1, m_Undef()))
01006     return Op1;
01007 
01008   // X / 0 -> undef, we don't need to preserve faults!
01009   if (match(Op1, m_Zero()))
01010     return UndefValue::get(Op1->getType());
01011 
01012   // undef / X -> 0
01013   if (match(Op0, m_Undef()))
01014     return Constant::getNullValue(Op0->getType());
01015 
01016   // 0 / X -> 0, we don't need to preserve faults!
01017   if (match(Op0, m_Zero()))
01018     return Op0;
01019 
01020   // X / 1 -> X
01021   if (match(Op1, m_One()))
01022     return Op0;
01023 
01024   if (Op0->getType()->isIntegerTy(1))
01025     // It can't be division by zero, hence it must be division by one.
01026     return Op0;
01027 
01028   // X / X -> 1
01029   if (Op0 == Op1)
01030     return ConstantInt::get(Op0->getType(), 1);
01031 
01032   // (X * Y) / Y -> X if the multiplication does not overflow.
01033   Value *X = nullptr, *Y = nullptr;
01034   if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
01035     if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
01036     OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0);
01037     // If the Mul knows it does not overflow, then we are good to go.
01038     if ((isSigned && Mul->hasNoSignedWrap()) ||
01039         (!isSigned && Mul->hasNoUnsignedWrap()))
01040       return X;
01041     // If X has the form X = A / Y then X * Y cannot overflow.
01042     if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X))
01043       if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y)
01044         return X;
01045   }
01046 
01047   // (X rem Y) / Y -> 0
01048   if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
01049       (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
01050     return Constant::getNullValue(Op0->getType());
01051 
01052   // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
01053   ConstantInt *C1, *C2;
01054   if (!isSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) &&
01055       match(Op1, m_ConstantInt(C2))) {
01056     bool Overflow;
01057     C1->getValue().umul_ov(C2->getValue(), Overflow);
01058     if (Overflow)
01059       return Constant::getNullValue(Op0->getType());
01060   }
01061 
01062   // If the operation is with the result of a select instruction, check whether
01063   // operating on either branch of the select always yields the same value.
01064   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01065     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
01066       return V;
01067 
01068   // If the operation is with the result of a phi instruction, check whether
01069   // operating on all incoming values of the phi always yields the same value.
01070   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01071     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
01072       return V;
01073 
01074   return nullptr;
01075 }
01076 
01077 /// SimplifySDivInst - Given operands for an SDiv, see if we can
01078 /// fold the result.  If not, this returns null.
01079 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q,
01080                                unsigned MaxRecurse) {
01081   if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse))
01082     return V;
01083 
01084   return nullptr;
01085 }
01086 
01087 Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout &DL,
01088                               const TargetLibraryInfo *TLI,
01089                               const DominatorTree *DT, AssumptionCache *AC,
01090                               const Instruction *CxtI) {
01091   return ::SimplifySDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
01092                             RecursionLimit);
01093 }
01094 
01095 /// SimplifyUDivInst - Given operands for a UDiv, see if we can
01096 /// fold the result.  If not, this returns null.
01097 static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q,
01098                                unsigned MaxRecurse) {
01099   if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse))
01100     return V;
01101 
01102   return nullptr;
01103 }
01104 
01105 Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout &DL,
01106                               const TargetLibraryInfo *TLI,
01107                               const DominatorTree *DT, AssumptionCache *AC,
01108                               const Instruction *CxtI) {
01109   return ::SimplifyUDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
01110                             RecursionLimit);
01111 }
01112 
01113 static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
01114                                const Query &Q, unsigned) {
01115   // undef / X -> undef    (the undef could be a snan).
01116   if (match(Op0, m_Undef()))
01117     return Op0;
01118 
01119   // X / undef -> undef
01120   if (match(Op1, m_Undef()))
01121     return Op1;
01122 
01123   // 0 / X -> 0
01124   // Requires that NaNs are off (X could be zero) and signed zeroes are
01125   // ignored (X could be positive or negative, so the output sign is unknown).
01126   if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero()))
01127     return Op0;
01128 
01129   if (FMF.noNaNs()) {
01130     // X / X -> 1.0 is legal when NaNs are ignored.
01131     if (Op0 == Op1)
01132       return ConstantFP::get(Op0->getType(), 1.0);
01133 
01134     // -X /  X -> -1.0 and
01135     //  X / -X -> -1.0 are legal when NaNs are ignored.
01136     // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored.
01137     if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) &&
01138          BinaryOperator::getFNegArgument(Op0) == Op1) ||
01139         (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) &&
01140          BinaryOperator::getFNegArgument(Op1) == Op0))
01141       return ConstantFP::get(Op0->getType(), -1.0);
01142   }
01143 
01144   return nullptr;
01145 }
01146 
01147 Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
01148                               const DataLayout &DL,
01149                               const TargetLibraryInfo *TLI,
01150                               const DominatorTree *DT, AssumptionCache *AC,
01151                               const Instruction *CxtI) {
01152   return ::SimplifyFDivInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
01153                             RecursionLimit);
01154 }
01155 
01156 /// SimplifyRem - Given operands for an SRem or URem, see if we can
01157 /// fold the result.  If not, this returns null.
01158 static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
01159                           const Query &Q, unsigned MaxRecurse) {
01160   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
01161     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
01162       Constant *Ops[] = { C0, C1 };
01163       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI);
01164     }
01165   }
01166 
01167   // X % undef -> undef
01168   if (match(Op1, m_Undef()))
01169     return Op1;
01170 
01171   // undef % X -> 0
01172   if (match(Op0, m_Undef()))
01173     return Constant::getNullValue(Op0->getType());
01174 
01175   // 0 % X -> 0, we don't need to preserve faults!
01176   if (match(Op0, m_Zero()))
01177     return Op0;
01178 
01179   // X % 0 -> undef, we don't need to preserve faults!
01180   if (match(Op1, m_Zero()))
01181     return UndefValue::get(Op0->getType());
01182 
01183   // X % 1 -> 0
01184   if (match(Op1, m_One()))
01185     return Constant::getNullValue(Op0->getType());
01186 
01187   if (Op0->getType()->isIntegerTy(1))
01188     // It can't be remainder by zero, hence it must be remainder by one.
01189     return Constant::getNullValue(Op0->getType());
01190 
01191   // X % X -> 0
01192   if (Op0 == Op1)
01193     return Constant::getNullValue(Op0->getType());
01194 
01195   // (X % Y) % Y -> X % Y
01196   if ((Opcode == Instruction::SRem &&
01197        match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
01198       (Opcode == Instruction::URem &&
01199        match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
01200     return Op0;
01201 
01202   // If the operation is with the result of a select instruction, check whether
01203   // operating on either branch of the select always yields the same value.
01204   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01205     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
01206       return V;
01207 
01208   // If the operation is with the result of a phi instruction, check whether
01209   // operating on all incoming values of the phi always yields the same value.
01210   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01211     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
01212       return V;
01213 
01214   return nullptr;
01215 }
01216 
01217 /// SimplifySRemInst - Given operands for an SRem, see if we can
01218 /// fold the result.  If not, this returns null.
01219 static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q,
01220                                unsigned MaxRecurse) {
01221   if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse))
01222     return V;
01223 
01224   return nullptr;
01225 }
01226 
01227 Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout &DL,
01228                               const TargetLibraryInfo *TLI,
01229                               const DominatorTree *DT, AssumptionCache *AC,
01230                               const Instruction *CxtI) {
01231   return ::SimplifySRemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
01232                             RecursionLimit);
01233 }
01234 
01235 /// SimplifyURemInst - Given operands for a URem, see if we can
01236 /// fold the result.  If not, this returns null.
01237 static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q,
01238                                unsigned MaxRecurse) {
01239   if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse))
01240     return V;
01241 
01242   return nullptr;
01243 }
01244 
01245 Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout &DL,
01246                               const TargetLibraryInfo *TLI,
01247                               const DominatorTree *DT, AssumptionCache *AC,
01248                               const Instruction *CxtI) {
01249   return ::SimplifyURemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
01250                             RecursionLimit);
01251 }
01252 
01253 static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
01254                                const Query &, unsigned) {
01255   // undef % X -> undef    (the undef could be a snan).
01256   if (match(Op0, m_Undef()))
01257     return Op0;
01258 
01259   // X % undef -> undef
01260   if (match(Op1, m_Undef()))
01261     return Op1;
01262 
01263   // 0 % X -> 0
01264   // Requires that NaNs are off (X could be zero) and signed zeroes are
01265   // ignored (X could be positive or negative, so the output sign is unknown).
01266   if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero()))
01267     return Op0;
01268 
01269   return nullptr;
01270 }
01271 
01272 Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
01273                               const DataLayout &DL,
01274                               const TargetLibraryInfo *TLI,
01275                               const DominatorTree *DT, AssumptionCache *AC,
01276                               const Instruction *CxtI) {
01277   return ::SimplifyFRemInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
01278                             RecursionLimit);
01279 }
01280 
01281 /// isUndefShift - Returns true if a shift by \c Amount always yields undef.
01282 static bool isUndefShift(Value *Amount) {
01283   Constant *C = dyn_cast<Constant>(Amount);
01284   if (!C)
01285     return false;
01286 
01287   // X shift by undef -> undef because it may shift by the bitwidth.
01288   if (isa<UndefValue>(C))
01289     return true;
01290 
01291   // Shifting by the bitwidth or more is undefined.
01292   if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
01293     if (CI->getValue().getLimitedValue() >=
01294         CI->getType()->getScalarSizeInBits())
01295       return true;
01296 
01297   // If all lanes of a vector shift are undefined the whole shift is.
01298   if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
01299     for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I)
01300       if (!isUndefShift(C->getAggregateElement(I)))
01301         return false;
01302     return true;
01303   }
01304 
01305   return false;
01306 }
01307 
01308 /// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can
01309 /// fold the result.  If not, this returns null.
01310 static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1,
01311                             const Query &Q, unsigned MaxRecurse) {
01312   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
01313     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
01314       Constant *Ops[] = { C0, C1 };
01315       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI);
01316     }
01317   }
01318 
01319   // 0 shift by X -> 0
01320   if (match(Op0, m_Zero()))
01321     return Op0;
01322 
01323   // X shift by 0 -> X
01324   if (match(Op1, m_Zero()))
01325     return Op0;
01326 
01327   // Fold undefined shifts.
01328   if (isUndefShift(Op1))
01329     return UndefValue::get(Op0->getType());
01330 
01331   // If the operation is with the result of a select instruction, check whether
01332   // operating on either branch of the select always yields the same value.
01333   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01334     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
01335       return V;
01336 
01337   // If the operation is with the result of a phi instruction, check whether
01338   // operating on all incoming values of the phi always yields the same value.
01339   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01340     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
01341       return V;
01342 
01343   return nullptr;
01344 }
01345 
01346 /// \brief Given operands for an Shl, LShr or AShr, see if we can
01347 /// fold the result.  If not, this returns null.
01348 static Value *SimplifyRightShift(unsigned Opcode, Value *Op0, Value *Op1,
01349                                  bool isExact, const Query &Q,
01350                                  unsigned MaxRecurse) {
01351   if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse))
01352     return V;
01353 
01354   // X >> X -> 0
01355   if (Op0 == Op1)
01356     return Constant::getNullValue(Op0->getType());
01357 
01358   // undef >> X -> 0
01359   // undef >> X -> undef (if it's exact)
01360   if (match(Op0, m_Undef()))
01361     return isExact ? Op0 : Constant::getNullValue(Op0->getType());
01362 
01363   // The low bit cannot be shifted out of an exact shift if it is set.
01364   if (isExact) {
01365     unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
01366     APInt Op0KnownZero(BitWidth, 0);
01367     APInt Op0KnownOne(BitWidth, 0);
01368     computeKnownBits(Op0, Op0KnownZero, Op0KnownOne, Q.DL, /*Depth=*/0, Q.AC,
01369                      Q.CxtI, Q.DT);
01370     if (Op0KnownOne[0])
01371       return Op0;
01372   }
01373 
01374   return nullptr;
01375 }
01376 
01377 /// SimplifyShlInst - Given operands for an Shl, see if we can
01378 /// fold the result.  If not, this returns null.
01379 static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
01380                               const Query &Q, unsigned MaxRecurse) {
01381   if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
01382     return V;
01383 
01384   // undef << X -> 0
01385   // undef << X -> undef if (if it's NSW/NUW)
01386   if (match(Op0, m_Undef()))
01387     return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
01388 
01389   // (X >> A) << A -> X
01390   Value *X;
01391   if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
01392     return X;
01393   return nullptr;
01394 }
01395 
01396 Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
01397                              const DataLayout &DL, const TargetLibraryInfo *TLI,
01398                              const DominatorTree *DT, AssumptionCache *AC,
01399                              const Instruction *CxtI) {
01400   return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI),
01401                            RecursionLimit);
01402 }
01403 
01404 /// SimplifyLShrInst - Given operands for an LShr, see if we can
01405 /// fold the result.  If not, this returns null.
01406 static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
01407                                const Query &Q, unsigned MaxRecurse) {
01408   if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q,
01409                                     MaxRecurse))
01410       return V;
01411 
01412   // (X << A) >> A -> X
01413   Value *X;
01414   if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1))))
01415     return X;
01416 
01417   return nullptr;
01418 }
01419 
01420 Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
01421                               const DataLayout &DL,
01422                               const TargetLibraryInfo *TLI,
01423                               const DominatorTree *DT, AssumptionCache *AC,
01424                               const Instruction *CxtI) {
01425   return ::SimplifyLShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI),
01426                             RecursionLimit);
01427 }
01428 
01429 /// SimplifyAShrInst - Given operands for an AShr, see if we can
01430 /// fold the result.  If not, this returns null.
01431 static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
01432                                const Query &Q, unsigned MaxRecurse) {
01433   if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q,
01434                                     MaxRecurse))
01435     return V;
01436 
01437   // all ones >>a X -> all ones
01438   if (match(Op0, m_AllOnes()))
01439     return Op0;
01440 
01441   // (X << A) >> A -> X
01442   Value *X;
01443   if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1))))
01444     return X;
01445 
01446   // Arithmetic shifting an all-sign-bit value is a no-op.
01447   unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
01448   if (NumSignBits == Op0->getType()->getScalarSizeInBits())
01449     return Op0;
01450 
01451   return nullptr;
01452 }
01453 
01454 Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
01455                               const DataLayout &DL,
01456                               const TargetLibraryInfo *TLI,
01457                               const DominatorTree *DT, AssumptionCache *AC,
01458                               const Instruction *CxtI) {
01459   return ::SimplifyAShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI),
01460                             RecursionLimit);
01461 }
01462 
01463 static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
01464                                          ICmpInst *UnsignedICmp, bool IsAnd) {
01465   Value *X, *Y;
01466 
01467   ICmpInst::Predicate EqPred;
01468   if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
01469       !ICmpInst::isEquality(EqPred))
01470     return nullptr;
01471 
01472   ICmpInst::Predicate UnsignedPred;
01473   if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
01474       ICmpInst::isUnsigned(UnsignedPred))
01475     ;
01476   else if (match(UnsignedICmp,
01477                  m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) &&
01478            ICmpInst::isUnsigned(UnsignedPred))
01479     UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
01480   else
01481     return nullptr;
01482 
01483   // X < Y && Y != 0  -->  X < Y
01484   // X < Y || Y != 0  -->  Y != 0
01485   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
01486     return IsAnd ? UnsignedICmp : ZeroICmp;
01487 
01488   // X >= Y || Y != 0  -->  true
01489   // X >= Y || Y == 0  -->  X >= Y
01490   if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) {
01491     if (EqPred == ICmpInst::ICMP_NE)
01492       return getTrue(UnsignedICmp->getType());
01493     return UnsignedICmp;
01494   }
01495 
01496   // X < Y && Y == 0  -->  false
01497   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
01498       IsAnd)
01499     return getFalse(UnsignedICmp->getType());
01500 
01501   return nullptr;
01502 }
01503 
01504 // Simplify (and (icmp ...) (icmp ...)) to true when we can tell that the range
01505 // of possible values cannot be satisfied.
01506 static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
01507   ICmpInst::Predicate Pred0, Pred1;
01508   ConstantInt *CI1, *CI2;
01509   Value *V;
01510 
01511   if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true))
01512     return X;
01513 
01514   if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)),
01515                          m_ConstantInt(CI2))))
01516    return nullptr;
01517 
01518   if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1))))
01519     return nullptr;
01520 
01521   Type *ITy = Op0->getType();
01522 
01523   auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
01524   bool isNSW = AddInst->hasNoSignedWrap();
01525   bool isNUW = AddInst->hasNoUnsignedWrap();
01526 
01527   const APInt &CI1V = CI1->getValue();
01528   const APInt &CI2V = CI2->getValue();
01529   const APInt Delta = CI2V - CI1V;
01530   if (CI1V.isStrictlyPositive()) {
01531     if (Delta == 2) {
01532       if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT)
01533         return getFalse(ITy);
01534       if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW)
01535         return getFalse(ITy);
01536     }
01537     if (Delta == 1) {
01538       if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT)
01539         return getFalse(ITy);
01540       if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW)
01541         return getFalse(ITy);
01542     }
01543   }
01544   if (CI1V.getBoolValue() && isNUW) {
01545     if (Delta == 2)
01546       if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT)
01547         return getFalse(ITy);
01548     if (Delta == 1)
01549       if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT)
01550         return getFalse(ITy);
01551   }
01552 
01553   return nullptr;
01554 }
01555 
01556 /// SimplifyAndInst - Given operands for an And, see if we can
01557 /// fold the result.  If not, this returns null.
01558 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q,
01559                               unsigned MaxRecurse) {
01560   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
01561     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
01562       Constant *Ops[] = { CLHS, CRHS };
01563       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
01564                                       Ops, Q.DL, Q.TLI);
01565     }
01566 
01567     // Canonicalize the constant to the RHS.
01568     std::swap(Op0, Op1);
01569   }
01570 
01571   // X & undef -> 0
01572   if (match(Op1, m_Undef()))
01573     return Constant::getNullValue(Op0->getType());
01574 
01575   // X & X = X
01576   if (Op0 == Op1)
01577     return Op0;
01578 
01579   // X & 0 = 0
01580   if (match(Op1, m_Zero()))
01581     return Op1;
01582 
01583   // X & -1 = X
01584   if (match(Op1, m_AllOnes()))
01585     return Op0;
01586 
01587   // A & ~A  =  ~A & A  =  0
01588   if (match(Op0, m_Not(m_Specific(Op1))) ||
01589       match(Op1, m_Not(m_Specific(Op0))))
01590     return Constant::getNullValue(Op0->getType());
01591 
01592   // (A | ?) & A = A
01593   Value *A = nullptr, *B = nullptr;
01594   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
01595       (A == Op1 || B == Op1))
01596     return Op1;
01597 
01598   // A & (A | ?) = A
01599   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
01600       (A == Op0 || B == Op0))
01601     return Op0;
01602 
01603   // A & (-A) = A if A is a power of two or zero.
01604   if (match(Op0, m_Neg(m_Specific(Op1))) ||
01605       match(Op1, m_Neg(m_Specific(Op0)))) {
01606     if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
01607                                Q.DT))
01608       return Op0;
01609     if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
01610                                Q.DT))
01611       return Op1;
01612   }
01613 
01614   if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
01615     if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
01616       if (Value *V = SimplifyAndOfICmps(ICILHS, ICIRHS))
01617         return V;
01618       if (Value *V = SimplifyAndOfICmps(ICIRHS, ICILHS))
01619         return V;
01620     }
01621   }
01622 
01623   // Try some generic simplifications for associative operations.
01624   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
01625                                           MaxRecurse))
01626     return V;
01627 
01628   // And distributes over Or.  Try some generic simplifications based on this.
01629   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
01630                              Q, MaxRecurse))
01631     return V;
01632 
01633   // And distributes over Xor.  Try some generic simplifications based on this.
01634   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
01635                              Q, MaxRecurse))
01636     return V;
01637 
01638   // If the operation is with the result of a select instruction, check whether
01639   // operating on either branch of the select always yields the same value.
01640   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01641     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
01642                                          MaxRecurse))
01643       return V;
01644 
01645   // If the operation is with the result of a phi instruction, check whether
01646   // operating on all incoming values of the phi always yields the same value.
01647   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01648     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
01649                                       MaxRecurse))
01650       return V;
01651 
01652   return nullptr;
01653 }
01654 
01655 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout &DL,
01656                              const TargetLibraryInfo *TLI,
01657                              const DominatorTree *DT, AssumptionCache *AC,
01658                              const Instruction *CxtI) {
01659   return ::SimplifyAndInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
01660                            RecursionLimit);
01661 }
01662 
01663 // Simplify (or (icmp ...) (icmp ...)) to true when we can tell that the union
01664 // contains all possible values.
01665 static Value *SimplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
01666   ICmpInst::Predicate Pred0, Pred1;
01667   ConstantInt *CI1, *CI2;
01668   Value *V;
01669 
01670   if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false))
01671     return X;
01672 
01673   if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)),
01674                          m_ConstantInt(CI2))))
01675    return nullptr;
01676 
01677   if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1))))
01678     return nullptr;
01679 
01680   Type *ITy = Op0->getType();
01681 
01682   auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
01683   bool isNSW = AddInst->hasNoSignedWrap();
01684   bool isNUW = AddInst->hasNoUnsignedWrap();
01685 
01686   const APInt &CI1V = CI1->getValue();
01687   const APInt &CI2V = CI2->getValue();
01688   const APInt Delta = CI2V - CI1V;
01689   if (CI1V.isStrictlyPositive()) {
01690     if (Delta == 2) {
01691       if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE)
01692         return getTrue(ITy);
01693       if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW)
01694         return getTrue(ITy);
01695     }
01696     if (Delta == 1) {
01697       if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE)
01698         return getTrue(ITy);
01699       if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW)
01700         return getTrue(ITy);
01701     }
01702   }
01703   if (CI1V.getBoolValue() && isNUW) {
01704     if (Delta == 2)
01705       if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE)
01706         return getTrue(ITy);
01707     if (Delta == 1)
01708       if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE)
01709         return getTrue(ITy);
01710   }
01711 
01712   return nullptr;
01713 }
01714 
01715 /// SimplifyOrInst - Given operands for an Or, see if we can
01716 /// fold the result.  If not, this returns null.
01717 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q,
01718                              unsigned MaxRecurse) {
01719   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
01720     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
01721       Constant *Ops[] = { CLHS, CRHS };
01722       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
01723                                       Ops, Q.DL, Q.TLI);
01724     }
01725 
01726     // Canonicalize the constant to the RHS.
01727     std::swap(Op0, Op1);
01728   }
01729 
01730   // X | undef -> -1
01731   if (match(Op1, m_Undef()))
01732     return Constant::getAllOnesValue(Op0->getType());
01733 
01734   // X | X = X
01735   if (Op0 == Op1)
01736     return Op0;
01737 
01738   // X | 0 = X
01739   if (match(Op1, m_Zero()))
01740     return Op0;
01741 
01742   // X | -1 = -1
01743   if (match(Op1, m_AllOnes()))
01744     return Op1;
01745 
01746   // A | ~A  =  ~A | A  =  -1
01747   if (match(Op0, m_Not(m_Specific(Op1))) ||
01748       match(Op1, m_Not(m_Specific(Op0))))
01749     return Constant::getAllOnesValue(Op0->getType());
01750 
01751   // (A & ?) | A = A
01752   Value *A = nullptr, *B = nullptr;
01753   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
01754       (A == Op1 || B == Op1))
01755     return Op1;
01756 
01757   // A | (A & ?) = A
01758   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
01759       (A == Op0 || B == Op0))
01760     return Op0;
01761 
01762   // ~(A & ?) | A = -1
01763   if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) &&
01764       (A == Op1 || B == Op1))
01765     return Constant::getAllOnesValue(Op1->getType());
01766 
01767   // A | ~(A & ?) = -1
01768   if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) &&
01769       (A == Op0 || B == Op0))
01770     return Constant::getAllOnesValue(Op0->getType());
01771 
01772   if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
01773     if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
01774       if (Value *V = SimplifyOrOfICmps(ICILHS, ICIRHS))
01775         return V;
01776       if (Value *V = SimplifyOrOfICmps(ICIRHS, ICILHS))
01777         return V;
01778     }
01779   }
01780 
01781   // Try some generic simplifications for associative operations.
01782   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
01783                                           MaxRecurse))
01784     return V;
01785 
01786   // Or distributes over And.  Try some generic simplifications based on this.
01787   if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
01788                              MaxRecurse))
01789     return V;
01790 
01791   // If the operation is with the result of a select instruction, check whether
01792   // operating on either branch of the select always yields the same value.
01793   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01794     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
01795                                          MaxRecurse))
01796       return V;
01797 
01798   // (A & C)|(B & D)
01799   Value *C = nullptr, *D = nullptr;
01800   if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
01801       match(Op1, m_And(m_Value(B), m_Value(D)))) {
01802     ConstantInt *C1 = dyn_cast<ConstantInt>(C);
01803     ConstantInt *C2 = dyn_cast<ConstantInt>(D);
01804     if (C1 && C2 && (C1->getValue() == ~C2->getValue())) {
01805       // (A & C1)|(B & C2)
01806       // If we have: ((V + N) & C1) | (V & C2)
01807       // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
01808       // replace with V+N.
01809       Value *V1, *V2;
01810       if ((C2->getValue() & (C2->getValue() + 1)) == 0 && // C2 == 0+1+
01811           match(A, m_Add(m_Value(V1), m_Value(V2)))) {
01812         // Add commutes, try both ways.
01813         if (V1 == B &&
01814             MaskedValueIsZero(V2, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
01815           return A;
01816         if (V2 == B &&
01817             MaskedValueIsZero(V1, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
01818           return A;
01819       }
01820       // Or commutes, try both ways.
01821       if ((C1->getValue() & (C1->getValue() + 1)) == 0 &&
01822           match(B, m_Add(m_Value(V1), m_Value(V2)))) {
01823         // Add commutes, try both ways.
01824         if (V1 == A &&
01825             MaskedValueIsZero(V2, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
01826           return B;
01827         if (V2 == A &&
01828             MaskedValueIsZero(V1, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
01829           return B;
01830       }
01831     }
01832   }
01833 
01834   // If the operation is with the result of a phi instruction, check whether
01835   // operating on all incoming values of the phi always yields the same value.
01836   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01837     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
01838       return V;
01839 
01840   return nullptr;
01841 }
01842 
01843 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout &DL,
01844                             const TargetLibraryInfo *TLI,
01845                             const DominatorTree *DT, AssumptionCache *AC,
01846                             const Instruction *CxtI) {
01847   return ::SimplifyOrInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
01848                           RecursionLimit);
01849 }
01850 
01851 /// SimplifyXorInst - Given operands for a Xor, see if we can
01852 /// fold the result.  If not, this returns null.
01853 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q,
01854                               unsigned MaxRecurse) {
01855   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
01856     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
01857       Constant *Ops[] = { CLHS, CRHS };
01858       return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
01859                                       Ops, Q.DL, Q.TLI);
01860     }
01861 
01862     // Canonicalize the constant to the RHS.
01863     std::swap(Op0, Op1);
01864   }
01865 
01866   // A ^ undef -> undef
01867   if (match(Op1, m_Undef()))
01868     return Op1;
01869 
01870   // A ^ 0 = A
01871   if (match(Op1, m_Zero()))
01872     return Op0;
01873 
01874   // A ^ A = 0
01875   if (Op0 == Op1)
01876     return Constant::getNullValue(Op0->getType());
01877 
01878   // A ^ ~A  =  ~A ^ A  =  -1
01879   if (match(Op0, m_Not(m_Specific(Op1))) ||
01880       match(Op1, m_Not(m_Specific(Op0))))
01881     return Constant::getAllOnesValue(Op0->getType());
01882 
01883   // Try some generic simplifications for associative operations.
01884   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
01885                                           MaxRecurse))
01886     return V;
01887 
01888   // Threading Xor over selects and phi nodes is pointless, so don't bother.
01889   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
01890   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
01891   // only if B and C are equal.  If B and C are equal then (since we assume
01892   // that operands have already been simplified) "select(cond, B, C)" should
01893   // have been simplified to the common value of B and C already.  Analysing
01894   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
01895   // for threading over phi nodes.
01896 
01897   return nullptr;
01898 }
01899 
01900 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout &DL,
01901                              const TargetLibraryInfo *TLI,
01902                              const DominatorTree *DT, AssumptionCache *AC,
01903                              const Instruction *CxtI) {
01904   return ::SimplifyXorInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
01905                            RecursionLimit);
01906 }
01907 
01908 static Type *GetCompareTy(Value *Op) {
01909   return CmpInst::makeCmpResultType(Op->getType());
01910 }
01911 
01912 /// ExtractEquivalentCondition - Rummage around inside V looking for something
01913 /// equivalent to the comparison "LHS Pred RHS".  Return such a value if found,
01914 /// otherwise return null.  Helper function for analyzing max/min idioms.
01915 static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
01916                                          Value *LHS, Value *RHS) {
01917   SelectInst *SI = dyn_cast<SelectInst>(V);
01918   if (!SI)
01919     return nullptr;
01920   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
01921   if (!Cmp)
01922     return nullptr;
01923   Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
01924   if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
01925     return Cmp;
01926   if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
01927       LHS == CmpRHS && RHS == CmpLHS)
01928     return Cmp;
01929   return nullptr;
01930 }
01931 
01932 // A significant optimization not implemented here is assuming that alloca
01933 // addresses are not equal to incoming argument values. They don't *alias*,
01934 // as we say, but that doesn't mean they aren't equal, so we take a
01935 // conservative approach.
01936 //
01937 // This is inspired in part by C++11 5.10p1:
01938 //   "Two pointers of the same type compare equal if and only if they are both
01939 //    null, both point to the same function, or both represent the same
01940 //    address."
01941 //
01942 // This is pretty permissive.
01943 //
01944 // It's also partly due to C11 6.5.9p6:
01945 //   "Two pointers compare equal if and only if both are null pointers, both are
01946 //    pointers to the same object (including a pointer to an object and a
01947 //    subobject at its beginning) or function, both are pointers to one past the
01948 //    last element of the same array object, or one is a pointer to one past the
01949 //    end of one array object and the other is a pointer to the start of a
01950 //    different array object that happens to immediately follow the first array
01951 //    object in the address space.)
01952 //
01953 // C11's version is more restrictive, however there's no reason why an argument
01954 // couldn't be a one-past-the-end value for a stack object in the caller and be
01955 // equal to the beginning of a stack object in the callee.
01956 //
01957 // If the C and C++ standards are ever made sufficiently restrictive in this
01958 // area, it may be possible to update LLVM's semantics accordingly and reinstate
01959 // this optimization.
01960 static Constant *computePointerICmp(const DataLayout &DL,
01961                                     const TargetLibraryInfo *TLI,
01962                                     CmpInst::Predicate Pred, Value *LHS,
01963                                     Value *RHS) {
01964   // First, skip past any trivial no-ops.
01965   LHS = LHS->stripPointerCasts();
01966   RHS = RHS->stripPointerCasts();
01967 
01968   // A non-null pointer is not equal to a null pointer.
01969   if (llvm::isKnownNonNull(LHS, TLI) && isa<ConstantPointerNull>(RHS) &&
01970       (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE))
01971     return ConstantInt::get(GetCompareTy(LHS),
01972                             !CmpInst::isTrueWhenEqual(Pred));
01973 
01974   // We can only fold certain predicates on pointer comparisons.
01975   switch (Pred) {
01976   default:
01977     return nullptr;
01978 
01979     // Equality comaprisons are easy to fold.
01980   case CmpInst::ICMP_EQ:
01981   case CmpInst::ICMP_NE:
01982     break;
01983 
01984     // We can only handle unsigned relational comparisons because 'inbounds' on
01985     // a GEP only protects against unsigned wrapping.
01986   case CmpInst::ICMP_UGT:
01987   case CmpInst::ICMP_UGE:
01988   case CmpInst::ICMP_ULT:
01989   case CmpInst::ICMP_ULE:
01990     // However, we have to switch them to their signed variants to handle
01991     // negative indices from the base pointer.
01992     Pred = ICmpInst::getSignedPredicate(Pred);
01993     break;
01994   }
01995 
01996   // Strip off any constant offsets so that we can reason about them.
01997   // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets
01998   // here and compare base addresses like AliasAnalysis does, however there are
01999   // numerous hazards. AliasAnalysis and its utilities rely on special rules
02000   // governing loads and stores which don't apply to icmps. Also, AliasAnalysis
02001   // doesn't need to guarantee pointer inequality when it says NoAlias.
02002   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
02003   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
02004 
02005   // If LHS and RHS are related via constant offsets to the same base
02006   // value, we can replace it with an icmp which just compares the offsets.
02007   if (LHS == RHS)
02008     return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
02009 
02010   // Various optimizations for (in)equality comparisons.
02011   if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
02012     // Different non-empty allocations that exist at the same time have
02013     // different addresses (if the program can tell). Global variables always
02014     // exist, so they always exist during the lifetime of each other and all
02015     // allocas. Two different allocas usually have different addresses...
02016     //
02017     // However, if there's an @llvm.stackrestore dynamically in between two
02018     // allocas, they may have the same address. It's tempting to reduce the
02019     // scope of the problem by only looking at *static* allocas here. That would
02020     // cover the majority of allocas while significantly reducing the likelihood
02021     // of having an @llvm.stackrestore pop up in the middle. However, it's not
02022     // actually impossible for an @llvm.stackrestore to pop up in the middle of
02023     // an entry block. Also, if we have a block that's not attached to a
02024     // function, we can't tell if it's "static" under the current definition.
02025     // Theoretically, this problem could be fixed by creating a new kind of
02026     // instruction kind specifically for static allocas. Such a new instruction
02027     // could be required to be at the top of the entry block, thus preventing it
02028     // from being subject to a @llvm.stackrestore. Instcombine could even
02029     // convert regular allocas into these special allocas. It'd be nifty.
02030     // However, until then, this problem remains open.
02031     //
02032     // So, we'll assume that two non-empty allocas have different addresses
02033     // for now.
02034     //
02035     // With all that, if the offsets are within the bounds of their allocations
02036     // (and not one-past-the-end! so we can't use inbounds!), and their
02037     // allocations aren't the same, the pointers are not equal.
02038     //
02039     // Note that it's not necessary to check for LHS being a global variable
02040     // address, due to canonicalization and constant folding.
02041     if (isa<AllocaInst>(LHS) &&
02042         (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
02043       ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset);
02044       ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset);
02045       uint64_t LHSSize, RHSSize;
02046       if (LHSOffsetCI && RHSOffsetCI &&
02047           getObjectSize(LHS, LHSSize, DL, TLI) &&
02048           getObjectSize(RHS, RHSSize, DL, TLI)) {
02049         const APInt &LHSOffsetValue = LHSOffsetCI->getValue();
02050         const APInt &RHSOffsetValue = RHSOffsetCI->getValue();
02051         if (!LHSOffsetValue.isNegative() &&
02052             !RHSOffsetValue.isNegative() &&
02053             LHSOffsetValue.ult(LHSSize) &&
02054             RHSOffsetValue.ult(RHSSize)) {
02055           return ConstantInt::get(GetCompareTy(LHS),
02056                                   !CmpInst::isTrueWhenEqual(Pred));
02057         }
02058       }
02059 
02060       // Repeat the above check but this time without depending on DataLayout
02061       // or being able to compute a precise size.
02062       if (!cast<PointerType>(LHS->getType())->isEmptyTy() &&
02063           !cast<PointerType>(RHS->getType())->isEmptyTy() &&
02064           LHSOffset->isNullValue() &&
02065           RHSOffset->isNullValue())
02066         return ConstantInt::get(GetCompareTy(LHS),
02067                                 !CmpInst::isTrueWhenEqual(Pred));
02068     }
02069 
02070     // Even if an non-inbounds GEP occurs along the path we can still optimize
02071     // equality comparisons concerning the result. We avoid walking the whole
02072     // chain again by starting where the last calls to
02073     // stripAndComputeConstantOffsets left off and accumulate the offsets.
02074     Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true);
02075     Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true);
02076     if (LHS == RHS)
02077       return ConstantExpr::getICmp(Pred,
02078                                    ConstantExpr::getAdd(LHSOffset, LHSNoBound),
02079                                    ConstantExpr::getAdd(RHSOffset, RHSNoBound));
02080 
02081     // If one side of the equality comparison must come from a noalias call
02082     // (meaning a system memory allocation function), and the other side must
02083     // come from a pointer that cannot overlap with dynamically-allocated
02084     // memory within the lifetime of the current function (allocas, byval
02085     // arguments, globals), then determine the comparison result here.
02086     SmallVector<Value *, 8> LHSUObjs, RHSUObjs;
02087     GetUnderlyingObjects(LHS, LHSUObjs, DL);
02088     GetUnderlyingObjects(RHS, RHSUObjs, DL);
02089 
02090     // Is the set of underlying objects all noalias calls?
02091     auto IsNAC = [](SmallVectorImpl<Value *> &Objects) {
02092       return std::all_of(Objects.begin(), Objects.end(),
02093                          [](Value *V){ return isNoAliasCall(V); });
02094     };
02095 
02096     // Is the set of underlying objects all things which must be disjoint from
02097     // noalias calls. For allocas, we consider only static ones (dynamic
02098     // allocas might be transformed into calls to malloc not simultaneously
02099     // live with the compared-to allocation). For globals, we exclude symbols
02100     // that might be resolve lazily to symbols in another dynamically-loaded
02101     // library (and, thus, could be malloc'ed by the implementation).
02102     auto IsAllocDisjoint = [](SmallVectorImpl<Value *> &Objects) {
02103       return std::all_of(Objects.begin(), Objects.end(),
02104                          [](Value *V){
02105                            if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
02106                              return AI->getParent() && AI->getParent()->getParent() &&
02107                                     AI->isStaticAlloca();
02108                            if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
02109                              return (GV->hasLocalLinkage() ||
02110                                      GV->hasHiddenVisibility() ||
02111                                      GV->hasProtectedVisibility() ||
02112                                      GV->hasUnnamedAddr()) &&
02113                                     !GV->isThreadLocal();
02114                            if (const Argument *A = dyn_cast<Argument>(V))
02115                              return A->hasByValAttr();
02116                            return false;
02117                          });
02118     };
02119 
02120     if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
02121         (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
02122         return ConstantInt::get(GetCompareTy(LHS),
02123                                 !CmpInst::isTrueWhenEqual(Pred));
02124   }
02125 
02126   // Otherwise, fail.
02127   return nullptr;
02128 }
02129 
02130 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
02131 /// fold the result.  If not, this returns null.
02132 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
02133                                const Query &Q, unsigned MaxRecurse) {
02134   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
02135   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
02136 
02137   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
02138     if (Constant *CRHS = dyn_cast<Constant>(RHS))
02139       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
02140 
02141     // If we have a constant, make sure it is on the RHS.
02142     std::swap(LHS, RHS);
02143     Pred = CmpInst::getSwappedPredicate(Pred);
02144   }
02145 
02146   Type *ITy = GetCompareTy(LHS); // The return type.
02147   Type *OpTy = LHS->getType();   // The operand type.
02148 
02149   // icmp X, X -> true/false
02150   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
02151   // because X could be 0.
02152   if (LHS == RHS || isa<UndefValue>(RHS))
02153     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
02154 
02155   // Special case logic when the operands have i1 type.
02156   if (OpTy->getScalarType()->isIntegerTy(1)) {
02157     switch (Pred) {
02158     default: break;
02159     case ICmpInst::ICMP_EQ:
02160       // X == 1 -> X
02161       if (match(RHS, m_One()))
02162         return LHS;
02163       break;
02164     case ICmpInst::ICMP_NE:
02165       // X != 0 -> X
02166       if (match(RHS, m_Zero()))
02167         return LHS;
02168       break;
02169     case ICmpInst::ICMP_UGT:
02170       // X >u 0 -> X
02171       if (match(RHS, m_Zero()))
02172         return LHS;
02173       break;
02174     case ICmpInst::ICMP_UGE:
02175       // X >=u 1 -> X
02176       if (match(RHS, m_One()))
02177         return LHS;
02178       break;
02179     case ICmpInst::ICMP_SLT:
02180       // X <s 0 -> X
02181       if (match(RHS, m_Zero()))
02182         return LHS;
02183       break;
02184     case ICmpInst::ICMP_SLE:
02185       // X <=s -1 -> X
02186       if (match(RHS, m_One()))
02187         return LHS;
02188       break;
02189     }
02190   }
02191 
02192   // If we are comparing with zero then try hard since this is a common case.
02193   if (match(RHS, m_Zero())) {
02194     bool LHSKnownNonNegative, LHSKnownNegative;
02195     switch (Pred) {
02196     default: llvm_unreachable("Unknown ICmp predicate!");
02197     case ICmpInst::ICMP_ULT:
02198       return getFalse(ITy);
02199     case ICmpInst::ICMP_UGE:
02200       return getTrue(ITy);
02201     case ICmpInst::ICMP_EQ:
02202     case ICmpInst::ICMP_ULE:
02203       if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
02204         return getFalse(ITy);
02205       break;
02206     case ICmpInst::ICMP_NE:
02207     case ICmpInst::ICMP_UGT:
02208       if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
02209         return getTrue(ITy);
02210       break;
02211     case ICmpInst::ICMP_SLT:
02212       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
02213                      Q.CxtI, Q.DT);
02214       if (LHSKnownNegative)
02215         return getTrue(ITy);
02216       if (LHSKnownNonNegative)
02217         return getFalse(ITy);
02218       break;
02219     case ICmpInst::ICMP_SLE:
02220       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
02221                      Q.CxtI, Q.DT);
02222       if (LHSKnownNegative)
02223         return getTrue(ITy);
02224       if (LHSKnownNonNegative &&
02225           isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
02226         return getFalse(ITy);
02227       break;
02228     case ICmpInst::ICMP_SGE:
02229       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
02230                      Q.CxtI, Q.DT);
02231       if (LHSKnownNegative)
02232         return getFalse(ITy);
02233       if (LHSKnownNonNegative)
02234         return getTrue(ITy);
02235       break;
02236     case ICmpInst::ICMP_SGT:
02237       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
02238                      Q.CxtI, Q.DT);
02239       if (LHSKnownNegative)
02240         return getFalse(ITy);
02241       if (LHSKnownNonNegative &&
02242           isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
02243         return getTrue(ITy);
02244       break;
02245     }
02246   }
02247 
02248   // See if we are doing a comparison with a constant integer.
02249   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
02250     // Rule out tautological comparisons (eg., ult 0 or uge 0).
02251     ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue());
02252     if (RHS_CR.isEmptySet())
02253       return ConstantInt::getFalse(CI->getContext());
02254     if (RHS_CR.isFullSet())
02255       return ConstantInt::getTrue(CI->getContext());
02256 
02257     // Many binary operators with constant RHS have easy to compute constant
02258     // range.  Use them to check whether the comparison is a tautology.
02259     unsigned Width = CI->getBitWidth();
02260     APInt Lower = APInt(Width, 0);
02261     APInt Upper = APInt(Width, 0);
02262     ConstantInt *CI2;
02263     if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) {
02264       // 'urem x, CI2' produces [0, CI2).
02265       Upper = CI2->getValue();
02266     } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) {
02267       // 'srem x, CI2' produces (-|CI2|, |CI2|).
02268       Upper = CI2->getValue().abs();
02269       Lower = (-Upper) + 1;
02270     } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) {
02271       // 'udiv CI2, x' produces [0, CI2].
02272       Upper = CI2->getValue() + 1;
02273     } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) {
02274       // 'udiv x, CI2' produces [0, UINT_MAX / CI2].
02275       APInt NegOne = APInt::getAllOnesValue(Width);
02276       if (!CI2->isZero())
02277         Upper = NegOne.udiv(CI2->getValue()) + 1;
02278     } else if (match(LHS, m_SDiv(m_ConstantInt(CI2), m_Value()))) {
02279       if (CI2->isMinSignedValue()) {
02280         // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2].
02281         Lower = CI2->getValue();
02282         Upper = Lower.lshr(1) + 1;
02283       } else {
02284         // 'sdiv CI2, x' produces [-|CI2|, |CI2|].
02285         Upper = CI2->getValue().abs() + 1;
02286         Lower = (-Upper) + 1;
02287       }
02288     } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) {
02289       APInt IntMin = APInt::getSignedMinValue(Width);
02290       APInt IntMax = APInt::getSignedMaxValue(Width);
02291       APInt Val = CI2->getValue();
02292       if (Val.isAllOnesValue()) {
02293         // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX]
02294         //    where CI2 != -1 and CI2 != 0 and CI2 != 1
02295         Lower = IntMin + 1;
02296         Upper = IntMax + 1;
02297       } else if (Val.countLeadingZeros() < Width - 1) {
02298         // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2]
02299         //    where CI2 != -1 and CI2 != 0 and CI2 != 1
02300         Lower = IntMin.sdiv(Val);
02301         Upper = IntMax.sdiv(Val);
02302         if (Lower.sgt(Upper))
02303           std::swap(Lower, Upper);
02304         Upper = Upper + 1;
02305         assert(Upper != Lower && "Upper part of range has wrapped!");
02306       }
02307     } else if (match(LHS, m_NUWShl(m_ConstantInt(CI2), m_Value()))) {
02308       // 'shl nuw CI2, x' produces [CI2, CI2 << CLZ(CI2)]
02309       Lower = CI2->getValue();
02310       Upper = Lower.shl(Lower.countLeadingZeros()) + 1;
02311     } else if (match(LHS, m_NSWShl(m_ConstantInt(CI2), m_Value()))) {
02312       if (CI2->isNegative()) {
02313         // 'shl nsw CI2, x' produces [CI2 << CLO(CI2)-1, CI2]
02314         unsigned ShiftAmount = CI2->getValue().countLeadingOnes() - 1;
02315         Lower = CI2->getValue().shl(ShiftAmount);
02316         Upper = CI2->getValue() + 1;
02317       } else {
02318         // 'shl nsw CI2, x' produces [CI2, CI2 << CLZ(CI2)-1]
02319         unsigned ShiftAmount = CI2->getValue().countLeadingZeros() - 1;
02320         Lower = CI2->getValue();
02321         Upper = CI2->getValue().shl(ShiftAmount) + 1;
02322       }
02323     } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) {
02324       // 'lshr x, CI2' produces [0, UINT_MAX >> CI2].
02325       APInt NegOne = APInt::getAllOnesValue(Width);
02326       if (CI2->getValue().ult(Width))
02327         Upper = NegOne.lshr(CI2->getValue()) + 1;
02328     } else if (match(LHS, m_LShr(m_ConstantInt(CI2), m_Value()))) {
02329       // 'lshr CI2, x' produces [CI2 >> (Width-1), CI2].
02330       unsigned ShiftAmount = Width - 1;
02331       if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact())
02332         ShiftAmount = CI2->getValue().countTrailingZeros();
02333       Lower = CI2->getValue().lshr(ShiftAmount);
02334       Upper = CI2->getValue() + 1;
02335     } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) {
02336       // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2].
02337       APInt IntMin = APInt::getSignedMinValue(Width);
02338       APInt IntMax = APInt::getSignedMaxValue(Width);
02339       if (CI2->getValue().ult(Width)) {
02340         Lower = IntMin.ashr(CI2->getValue());
02341         Upper = IntMax.ashr(CI2->getValue()) + 1;
02342       }
02343     } else if (match(LHS, m_AShr(m_ConstantInt(CI2), m_Value()))) {
02344       unsigned ShiftAmount = Width - 1;
02345       if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact())
02346         ShiftAmount = CI2->getValue().countTrailingZeros();
02347       if (CI2->isNegative()) {
02348         // 'ashr CI2, x' produces [CI2, CI2 >> (Width-1)]
02349         Lower = CI2->getValue();
02350         Upper = CI2->getValue().ashr(ShiftAmount) + 1;
02351       } else {
02352         // 'ashr CI2, x' produces [CI2 >> (Width-1), CI2]
02353         Lower = CI2->getValue().ashr(ShiftAmount);
02354         Upper = CI2->getValue() + 1;
02355       }
02356     } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) {
02357       // 'or x, CI2' produces [CI2, UINT_MAX].
02358       Lower = CI2->getValue();
02359     } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) {
02360       // 'and x, CI2' produces [0, CI2].
02361       Upper = CI2->getValue() + 1;
02362     }
02363     if (Lower != Upper) {
02364       ConstantRange LHS_CR = ConstantRange(Lower, Upper);
02365       if (RHS_CR.contains(LHS_CR))
02366         return ConstantInt::getTrue(RHS->getContext());
02367       if (RHS_CR.inverse().contains(LHS_CR))
02368         return ConstantInt::getFalse(RHS->getContext());
02369     }
02370   }
02371 
02372   // Compare of cast, for example (zext X) != 0 -> X != 0
02373   if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
02374     Instruction *LI = cast<CastInst>(LHS);
02375     Value *SrcOp = LI->getOperand(0);
02376     Type *SrcTy = SrcOp->getType();
02377     Type *DstTy = LI->getType();
02378 
02379     // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
02380     // if the integer type is the same size as the pointer type.
02381     if (MaxRecurse && isa<PtrToIntInst>(LI) &&
02382         Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) {
02383       if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
02384         // Transfer the cast to the constant.
02385         if (Value *V = SimplifyICmpInst(Pred, SrcOp,
02386                                         ConstantExpr::getIntToPtr(RHSC, SrcTy),
02387                                         Q, MaxRecurse-1))
02388           return V;
02389       } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
02390         if (RI->getOperand(0)->getType() == SrcTy)
02391           // Compare without the cast.
02392           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
02393                                           Q, MaxRecurse-1))
02394             return V;
02395       }
02396     }
02397 
02398     if (isa<ZExtInst>(LHS)) {
02399       // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
02400       // same type.
02401       if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
02402         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
02403           // Compare X and Y.  Note that signed predicates become unsigned.
02404           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
02405                                           SrcOp, RI->getOperand(0), Q,
02406                                           MaxRecurse-1))
02407             return V;
02408       }
02409       // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
02410       // too.  If not, then try to deduce the result of the comparison.
02411       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
02412         // Compute the constant that would happen if we truncated to SrcTy then
02413         // reextended to DstTy.
02414         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
02415         Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
02416 
02417         // If the re-extended constant didn't change then this is effectively
02418         // also a case of comparing two zero-extended values.
02419         if (RExt == CI && MaxRecurse)
02420           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
02421                                         SrcOp, Trunc, Q, MaxRecurse-1))
02422             return V;
02423 
02424         // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
02425         // there.  Use this to work out the result of the comparison.
02426         if (RExt != CI) {
02427           switch (Pred) {
02428           default: llvm_unreachable("Unknown ICmp predicate!");
02429           // LHS <u RHS.
02430           case ICmpInst::ICMP_EQ:
02431           case ICmpInst::ICMP_UGT:
02432           case ICmpInst::ICMP_UGE:
02433             return ConstantInt::getFalse(CI->getContext());
02434 
02435           case ICmpInst::ICMP_NE:
02436           case ICmpInst::ICMP_ULT:
02437           case ICmpInst::ICMP_ULE:
02438             return ConstantInt::getTrue(CI->getContext());
02439 
02440           // LHS is non-negative.  If RHS is negative then LHS >s LHS.  If RHS
02441           // is non-negative then LHS <s RHS.
02442           case ICmpInst::ICMP_SGT:
02443           case ICmpInst::ICMP_SGE:
02444             return CI->getValue().isNegative() ?
02445               ConstantInt::getTrue(CI->getContext()) :
02446               ConstantInt::getFalse(CI->getContext());
02447 
02448           case ICmpInst::ICMP_SLT:
02449           case ICmpInst::ICMP_SLE:
02450             return CI->getValue().isNegative() ?
02451               ConstantInt::getFalse(CI->getContext()) :
02452               ConstantInt::getTrue(CI->getContext());
02453           }
02454         }
02455       }
02456     }
02457 
02458     if (isa<SExtInst>(LHS)) {
02459       // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
02460       // same type.
02461       if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
02462         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
02463           // Compare X and Y.  Note that the predicate does not change.
02464           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
02465                                           Q, MaxRecurse-1))
02466             return V;
02467       }
02468       // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
02469       // too.  If not, then try to deduce the result of the comparison.
02470       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
02471         // Compute the constant that would happen if we truncated to SrcTy then
02472         // reextended to DstTy.
02473         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
02474         Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
02475 
02476         // If the re-extended constant didn't change then this is effectively
02477         // also a case of comparing two sign-extended values.
02478         if (RExt == CI && MaxRecurse)
02479           if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1))
02480             return V;
02481 
02482         // Otherwise the upper bits of LHS are all equal, while RHS has varying
02483         // bits there.  Use this to work out the result of the comparison.
02484         if (RExt != CI) {
02485           switch (Pred) {
02486           default: llvm_unreachable("Unknown ICmp predicate!");
02487           case ICmpInst::ICMP_EQ:
02488             return ConstantInt::getFalse(CI->getContext());
02489           case ICmpInst::ICMP_NE:
02490             return ConstantInt::getTrue(CI->getContext());
02491 
02492           // If RHS is non-negative then LHS <s RHS.  If RHS is negative then
02493           // LHS >s RHS.
02494           case ICmpInst::ICMP_SGT:
02495           case ICmpInst::ICMP_SGE:
02496             return CI->getValue().isNegative() ?
02497               ConstantInt::getTrue(CI->getContext()) :
02498               ConstantInt::getFalse(CI->getContext());
02499           case ICmpInst::ICMP_SLT:
02500           case ICmpInst::ICMP_SLE:
02501             return CI->getValue().isNegative() ?
02502               ConstantInt::getFalse(CI->getContext()) :
02503               ConstantInt::getTrue(CI->getContext());
02504 
02505           // If LHS is non-negative then LHS <u RHS.  If LHS is negative then
02506           // LHS >u RHS.
02507           case ICmpInst::ICMP_UGT:
02508           case ICmpInst::ICMP_UGE:
02509             // Comparison is true iff the LHS <s 0.
02510             if (MaxRecurse)
02511               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
02512                                               Constant::getNullValue(SrcTy),
02513                                               Q, MaxRecurse-1))
02514                 return V;
02515             break;
02516           case ICmpInst::ICMP_ULT:
02517           case ICmpInst::ICMP_ULE:
02518             // Comparison is true iff the LHS >=s 0.
02519             if (MaxRecurse)
02520               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
02521                                               Constant::getNullValue(SrcTy),
02522                                               Q, MaxRecurse-1))
02523                 return V;
02524             break;
02525           }
02526         }
02527       }
02528     }
02529   }
02530 
02531   // Special logic for binary operators.
02532   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
02533   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
02534   if (MaxRecurse && (LBO || RBO)) {
02535     // Analyze the case when either LHS or RHS is an add instruction.
02536     Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
02537     // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
02538     bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
02539     if (LBO && LBO->getOpcode() == Instruction::Add) {
02540       A = LBO->getOperand(0); B = LBO->getOperand(1);
02541       NoLHSWrapProblem = ICmpInst::isEquality(Pred) ||
02542         (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
02543         (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
02544     }
02545     if (RBO && RBO->getOpcode() == Instruction::Add) {
02546       C = RBO->getOperand(0); D = RBO->getOperand(1);
02547       NoRHSWrapProblem = ICmpInst::isEquality(Pred) ||
02548         (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
02549         (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
02550     }
02551 
02552     // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
02553     if ((A == RHS || B == RHS) && NoLHSWrapProblem)
02554       if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
02555                                       Constant::getNullValue(RHS->getType()),
02556                                       Q, MaxRecurse-1))
02557         return V;
02558 
02559     // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
02560     if ((C == LHS || D == LHS) && NoRHSWrapProblem)
02561       if (Value *V = SimplifyICmpInst(Pred,
02562                                       Constant::getNullValue(LHS->getType()),
02563                                       C == LHS ? D : C, Q, MaxRecurse-1))
02564         return V;
02565 
02566     // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
02567     if (A && C && (A == C || A == D || B == C || B == D) &&
02568         NoLHSWrapProblem && NoRHSWrapProblem) {
02569       // Determine Y and Z in the form icmp (X+Y), (X+Z).
02570       Value *Y, *Z;
02571       if (A == C) {
02572         // C + B == C + D  ->  B == D
02573         Y = B;
02574         Z = D;
02575       } else if (A == D) {
02576         // D + B == C + D  ->  B == C
02577         Y = B;
02578         Z = C;
02579       } else if (B == C) {
02580         // A + C == C + D  ->  A == D
02581         Y = A;
02582         Z = D;
02583       } else {
02584         assert(B == D);
02585         // A + D == C + D  ->  A == C
02586         Y = A;
02587         Z = C;
02588       }
02589       if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1))
02590         return V;
02591     }
02592   }
02593 
02594   // icmp pred (or X, Y), X
02595   if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)),
02596                                     m_Or(m_Specific(RHS), m_Value())))) {
02597     if (Pred == ICmpInst::ICMP_ULT)
02598       return getFalse(ITy);
02599     if (Pred == ICmpInst::ICMP_UGE)
02600       return getTrue(ITy);
02601   }
02602   // icmp pred X, (or X, Y)
02603   if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)),
02604                                     m_Or(m_Specific(LHS), m_Value())))) {
02605     if (Pred == ICmpInst::ICMP_ULE)
02606       return getTrue(ITy);
02607     if (Pred == ICmpInst::ICMP_UGT)
02608       return getFalse(ITy);
02609   }
02610 
02611   // icmp pred (and X, Y), X
02612   if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)),
02613                                     m_And(m_Specific(RHS), m_Value())))) {
02614     if (Pred == ICmpInst::ICMP_UGT)
02615       return getFalse(ITy);
02616     if (Pred == ICmpInst::ICMP_ULE)
02617       return getTrue(ITy);
02618   }
02619   // icmp pred X, (and X, Y)
02620   if (RBO && match(RBO, m_CombineOr(m_And(m_Value(), m_Specific(LHS)),
02621                                     m_And(m_Specific(LHS), m_Value())))) {
02622     if (Pred == ICmpInst::ICMP_UGE)
02623       return getTrue(ITy);
02624     if (Pred == ICmpInst::ICMP_ULT)
02625       return getFalse(ITy);
02626   }
02627 
02628   // 0 - (zext X) pred C
02629   if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
02630     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
02631       if (RHSC->getValue().isStrictlyPositive()) {
02632         if (Pred == ICmpInst::ICMP_SLT)
02633           return ConstantInt::getTrue(RHSC->getContext());
02634         if (Pred == ICmpInst::ICMP_SGE)
02635           return ConstantInt::getFalse(RHSC->getContext());
02636         if (Pred == ICmpInst::ICMP_EQ)
02637           return ConstantInt::getFalse(RHSC->getContext());
02638         if (Pred == ICmpInst::ICMP_NE)
02639           return ConstantInt::getTrue(RHSC->getContext());
02640       }
02641       if (RHSC->getValue().isNonNegative()) {
02642         if (Pred == ICmpInst::ICMP_SLE)
02643           return ConstantInt::getTrue(RHSC->getContext());
02644         if (Pred == ICmpInst::ICMP_SGT)
02645           return ConstantInt::getFalse(RHSC->getContext());
02646       }
02647     }
02648   }
02649 
02650   // icmp pred (urem X, Y), Y
02651   if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
02652     bool KnownNonNegative, KnownNegative;
02653     switch (Pred) {
02654     default:
02655       break;
02656     case ICmpInst::ICMP_SGT:
02657     case ICmpInst::ICMP_SGE:
02658       ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
02659                      Q.CxtI, Q.DT);
02660       if (!KnownNonNegative)
02661         break;
02662       // fall-through
02663     case ICmpInst::ICMP_EQ:
02664     case ICmpInst::ICMP_UGT:
02665     case ICmpInst::ICMP_UGE:
02666       return getFalse(ITy);
02667     case ICmpInst::ICMP_SLT:
02668     case ICmpInst::ICMP_SLE:
02669       ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
02670                      Q.CxtI, Q.DT);
02671       if (!KnownNonNegative)
02672         break;
02673       // fall-through
02674     case ICmpInst::ICMP_NE:
02675     case ICmpInst::ICMP_ULT:
02676     case ICmpInst::ICMP_ULE:
02677       return getTrue(ITy);
02678     }
02679   }
02680 
02681   // icmp pred X, (urem Y, X)
02682   if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
02683     bool KnownNonNegative, KnownNegative;
02684     switch (Pred) {
02685     default:
02686       break;
02687     case ICmpInst::ICMP_SGT:
02688     case ICmpInst::ICMP_SGE:
02689       ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
02690                      Q.CxtI, Q.DT);
02691       if (!KnownNonNegative)
02692         break;
02693       // fall-through
02694     case ICmpInst::ICMP_NE:
02695     case ICmpInst::ICMP_UGT:
02696     case ICmpInst::ICMP_UGE:
02697       return getTrue(ITy);
02698     case ICmpInst::ICMP_SLT:
02699     case ICmpInst::ICMP_SLE:
02700       ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
02701                      Q.CxtI, Q.DT);
02702       if (!KnownNonNegative)
02703         break;
02704       // fall-through
02705     case ICmpInst::ICMP_EQ:
02706     case ICmpInst::ICMP_ULT:
02707     case ICmpInst::ICMP_ULE:
02708       return getFalse(ITy);
02709     }
02710   }
02711 
02712   // x udiv y <=u x.
02713   if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
02714     // icmp pred (X /u Y), X
02715     if (Pred == ICmpInst::ICMP_UGT)
02716       return getFalse(ITy);
02717     if (Pred == ICmpInst::ICMP_ULE)
02718       return getTrue(ITy);
02719   }
02720 
02721   // handle:
02722   //   CI2 << X == CI
02723   //   CI2 << X != CI
02724   //
02725   //   where CI2 is a power of 2 and CI isn't
02726   if (auto *CI = dyn_cast<ConstantInt>(RHS)) {
02727     const APInt *CI2Val, *CIVal = &CI->getValue();
02728     if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) &&
02729         CI2Val->isPowerOf2()) {
02730       if (!CIVal->isPowerOf2()) {
02731         // CI2 << X can equal zero in some circumstances,
02732         // this simplification is unsafe if CI is zero.
02733         //
02734         // We know it is safe if:
02735         // - The shift is nsw, we can't shift out the one bit.
02736         // - The shift is nuw, we can't shift out the one bit.
02737         // - CI2 is one
02738         // - CI isn't zero
02739         if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() ||
02740             *CI2Val == 1 || !CI->isZero()) {
02741           if (Pred == ICmpInst::ICMP_EQ)
02742             return ConstantInt::getFalse(RHS->getContext());
02743           if (Pred == ICmpInst::ICMP_NE)
02744             return ConstantInt::getTrue(RHS->getContext());
02745         }
02746       }
02747       if (CIVal->isSignBit() && *CI2Val == 1) {
02748         if (Pred == ICmpInst::ICMP_UGT)
02749           return ConstantInt::getFalse(RHS->getContext());
02750         if (Pred == ICmpInst::ICMP_ULE)
02751           return ConstantInt::getTrue(RHS->getContext());
02752       }
02753     }
02754   }
02755 
02756   if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
02757       LBO->getOperand(1) == RBO->getOperand(1)) {
02758     switch (LBO->getOpcode()) {
02759     default: break;
02760     case Instruction::UDiv:
02761     case Instruction::LShr:
02762       if (ICmpInst::isSigned(Pred))
02763         break;
02764       // fall-through
02765     case Instruction::SDiv:
02766     case Instruction::AShr:
02767       if (!LBO->isExact() || !RBO->isExact())
02768         break;
02769       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
02770                                       RBO->getOperand(0), Q, MaxRecurse-1))
02771         return V;
02772       break;
02773     case Instruction::Shl: {
02774       bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
02775       bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
02776       if (!NUW && !NSW)
02777         break;
02778       if (!NSW && ICmpInst::isSigned(Pred))
02779         break;
02780       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
02781                                       RBO->getOperand(0), Q, MaxRecurse-1))
02782         return V;
02783       break;
02784     }
02785     }
02786   }
02787 
02788   // Simplify comparisons involving max/min.
02789   Value *A, *B;
02790   CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
02791   CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
02792 
02793   // Signed variants on "max(a,b)>=a -> true".
02794   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
02795     if (A != RHS) std::swap(A, B); // smax(A, B) pred A.
02796     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
02797     // We analyze this as smax(A, B) pred A.
02798     P = Pred;
02799   } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
02800              (A == LHS || B == LHS)) {
02801     if (A != LHS) std::swap(A, B); // A pred smax(A, B).
02802     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
02803     // We analyze this as smax(A, B) swapped-pred A.
02804     P = CmpInst::getSwappedPredicate(Pred);
02805   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
02806              (A == RHS || B == RHS)) {
02807     if (A != RHS) std::swap(A, B); // smin(A, B) pred A.
02808     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
02809     // We analyze this as smax(-A, -B) swapped-pred -A.
02810     // Note that we do not need to actually form -A or -B thanks to EqP.
02811     P = CmpInst::getSwappedPredicate(Pred);
02812   } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
02813              (A == LHS || B == LHS)) {
02814     if (A != LHS) std::swap(A, B); // A pred smin(A, B).
02815     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
02816     // We analyze this as smax(-A, -B) pred -A.
02817     // Note that we do not need to actually form -A or -B thanks to EqP.
02818     P = Pred;
02819   }
02820   if (P != CmpInst::BAD_ICMP_PREDICATE) {
02821     // Cases correspond to "max(A, B) p A".
02822     switch (P) {
02823     default:
02824       break;
02825     case CmpInst::ICMP_EQ:
02826     case CmpInst::ICMP_SLE:
02827       // Equivalent to "A EqP B".  This may be the same as the condition tested
02828       // in the max/min; if so, we can just return that.
02829       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
02830         return V;
02831       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
02832         return V;
02833       // Otherwise, see if "A EqP B" simplifies.
02834       if (MaxRecurse)
02835         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1))
02836           return V;
02837       break;
02838     case CmpInst::ICMP_NE:
02839     case CmpInst::ICMP_SGT: {
02840       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
02841       // Equivalent to "A InvEqP B".  This may be the same as the condition
02842       // tested in the max/min; if so, we can just return that.
02843       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
02844         return V;
02845       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
02846         return V;
02847       // Otherwise, see if "A InvEqP B" simplifies.
02848       if (MaxRecurse)
02849         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1))
02850           return V;
02851       break;
02852     }
02853     case CmpInst::ICMP_SGE:
02854       // Always true.
02855       return getTrue(ITy);
02856     case CmpInst::ICMP_SLT:
02857       // Always false.
02858       return getFalse(ITy);
02859     }
02860   }
02861 
02862   // Unsigned variants on "max(a,b)>=a -> true".
02863   P = CmpInst::BAD_ICMP_PREDICATE;
02864   if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
02865     if (A != RHS) std::swap(A, B); // umax(A, B) pred A.
02866     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
02867     // We analyze this as umax(A, B) pred A.
02868     P = Pred;
02869   } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
02870              (A == LHS || B == LHS)) {
02871     if (A != LHS) std::swap(A, B); // A pred umax(A, B).
02872     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
02873     // We analyze this as umax(A, B) swapped-pred A.
02874     P = CmpInst::getSwappedPredicate(Pred);
02875   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
02876              (A == RHS || B == RHS)) {
02877     if (A != RHS) std::swap(A, B); // umin(A, B) pred A.
02878     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
02879     // We analyze this as umax(-A, -B) swapped-pred -A.
02880     // Note that we do not need to actually form -A or -B thanks to EqP.
02881     P = CmpInst::getSwappedPredicate(Pred);
02882   } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
02883              (A == LHS || B == LHS)) {
02884     if (A != LHS) std::swap(A, B); // A pred umin(A, B).
02885     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
02886     // We analyze this as umax(-A, -B) pred -A.
02887     // Note that we do not need to actually form -A or -B thanks to EqP.
02888     P = Pred;
02889   }
02890   if (P != CmpInst::BAD_ICMP_PREDICATE) {
02891     // Cases correspond to "max(A, B) p A".
02892     switch (P) {
02893     default:
02894       break;
02895     case CmpInst::ICMP_EQ:
02896     case CmpInst::ICMP_ULE:
02897       // Equivalent to "A EqP B".  This may be the same as the condition tested
02898       // in the max/min; if so, we can just return that.
02899       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
02900         return V;
02901       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
02902         return V;
02903       // Otherwise, see if "A EqP B" simplifies.
02904       if (MaxRecurse)
02905         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1))
02906           return V;
02907       break;
02908     case CmpInst::ICMP_NE:
02909     case CmpInst::ICMP_UGT: {
02910       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
02911       // Equivalent to "A InvEqP B".  This may be the same as the condition
02912       // tested in the max/min; if so, we can just return that.
02913       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
02914         return V;
02915       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
02916         return V;
02917       // Otherwise, see if "A InvEqP B" simplifies.
02918       if (MaxRecurse)
02919         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1))
02920           return V;
02921       break;
02922     }
02923     case CmpInst::ICMP_UGE:
02924       // Always true.
02925       return getTrue(ITy);
02926     case CmpInst::ICMP_ULT:
02927       // Always false.
02928       return getFalse(ITy);
02929     }
02930   }
02931 
02932   // Variants on "max(x,y) >= min(x,z)".
02933   Value *C, *D;
02934   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
02935       match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
02936       (A == C || A == D || B == C || B == D)) {
02937     // max(x, ?) pred min(x, ?).
02938     if (Pred == CmpInst::ICMP_SGE)
02939       // Always true.
02940       return getTrue(ITy);
02941     if (Pred == CmpInst::ICMP_SLT)
02942       // Always false.
02943       return getFalse(ITy);
02944   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
02945              match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
02946              (A == C || A == D || B == C || B == D)) {
02947     // min(x, ?) pred max(x, ?).
02948     if (Pred == CmpInst::ICMP_SLE)
02949       // Always true.
02950       return getTrue(ITy);
02951     if (Pred == CmpInst::ICMP_SGT)
02952       // Always false.
02953       return getFalse(ITy);
02954   } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
02955              match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
02956              (A == C || A == D || B == C || B == D)) {
02957     // max(x, ?) pred min(x, ?).
02958     if (Pred == CmpInst::ICMP_UGE)
02959       // Always true.
02960       return getTrue(ITy);
02961     if (Pred == CmpInst::ICMP_ULT)
02962       // Always false.
02963       return getFalse(ITy);
02964   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
02965              match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
02966              (A == C || A == D || B == C || B == D)) {
02967     // min(x, ?) pred max(x, ?).
02968     if (Pred == CmpInst::ICMP_ULE)
02969       // Always true.
02970       return getTrue(ITy);
02971     if (Pred == CmpInst::ICMP_UGT)
02972       // Always false.
02973       return getFalse(ITy);
02974   }
02975 
02976   // Simplify comparisons of related pointers using a powerful, recursive
02977   // GEP-walk when we have target data available..
02978   if (LHS->getType()->isPointerTy())
02979     if (Constant *C = computePointerICmp(Q.DL, Q.TLI, Pred, LHS, RHS))
02980       return C;
02981 
02982   if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
02983     if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
02984       if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
02985           GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
02986           (ICmpInst::isEquality(Pred) ||
02987            (GLHS->isInBounds() && GRHS->isInBounds() &&
02988             Pred == ICmpInst::getSignedPredicate(Pred)))) {
02989         // The bases are equal and the indices are constant.  Build a constant
02990         // expression GEP with the same indices and a null base pointer to see
02991         // what constant folding can make out of it.
02992         Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
02993         SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
02994         Constant *NewLHS = ConstantExpr::getGetElementPtr(
02995             GLHS->getSourceElementType(), Null, IndicesLHS);
02996 
02997         SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
02998         Constant *NewRHS = ConstantExpr::getGetElementPtr(
02999             GLHS->getSourceElementType(), Null, IndicesRHS);
03000         return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
03001       }
03002     }
03003   }
03004 
03005   // If a bit is known to be zero for A and known to be one for B,
03006   // then A and B cannot be equal.
03007   if (ICmpInst::isEquality(Pred)) {
03008     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
03009       uint32_t BitWidth = CI->getBitWidth();
03010       APInt LHSKnownZero(BitWidth, 0);
03011       APInt LHSKnownOne(BitWidth, 0);
03012       computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, Q.DL, /*Depth=*/0, Q.AC,
03013                        Q.CxtI, Q.DT);
03014       const APInt &RHSVal = CI->getValue();
03015       if (((LHSKnownZero & RHSVal) != 0) || ((LHSKnownOne & ~RHSVal) != 0))
03016         return Pred == ICmpInst::ICMP_EQ
03017                    ? ConstantInt::getFalse(CI->getContext())
03018                    : ConstantInt::getTrue(CI->getContext());
03019     }
03020   }
03021 
03022   // If the comparison is with the result of a select instruction, check whether
03023   // comparing with either branch of the select always yields the same value.
03024   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
03025     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
03026       return V;
03027 
03028   // If the comparison is with the result of a phi instruction, check whether
03029   // doing the compare with each incoming phi value yields a common result.
03030   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
03031     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
03032       return V;
03033 
03034   return nullptr;
03035 }
03036 
03037 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
03038                               const DataLayout &DL,
03039                               const TargetLibraryInfo *TLI,
03040                               const DominatorTree *DT, AssumptionCache *AC,
03041                               Instruction *CxtI) {
03042   return ::SimplifyICmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI),
03043                             RecursionLimit);
03044 }
03045 
03046 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
03047 /// fold the result.  If not, this returns null.
03048 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
03049                                const Query &Q, unsigned MaxRecurse) {
03050   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
03051   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
03052 
03053   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
03054     if (Constant *CRHS = dyn_cast<Constant>(RHS))
03055       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
03056 
03057     // If we have a constant, make sure it is on the RHS.
03058     std::swap(LHS, RHS);
03059     Pred = CmpInst::getSwappedPredicate(Pred);
03060   }
03061 
03062   // Fold trivial predicates.
03063   if (Pred == FCmpInst::FCMP_FALSE)
03064     return ConstantInt::get(GetCompareTy(LHS), 0);
03065   if (Pred == FCmpInst::FCMP_TRUE)
03066     return ConstantInt::get(GetCompareTy(LHS), 1);
03067 
03068   // fcmp pred x, undef  and  fcmp pred undef, x
03069   // fold to true if unordered, false if ordered
03070   if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) {
03071     // Choosing NaN for the undef will always make unordered comparison succeed
03072     // and ordered comparison fail.
03073     return ConstantInt::get(GetCompareTy(LHS), CmpInst::isUnordered(Pred));
03074   }
03075 
03076   // fcmp x,x -> true/false.  Not all compares are foldable.
03077   if (LHS == RHS) {
03078     if (CmpInst::isTrueWhenEqual(Pred))
03079       return ConstantInt::get(GetCompareTy(LHS), 1);
03080     if (CmpInst::isFalseWhenEqual(Pred))
03081       return ConstantInt::get(GetCompareTy(LHS), 0);
03082   }
03083 
03084   // Handle fcmp with constant RHS
03085   if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) {
03086     // If the constant is a nan, see if we can fold the comparison based on it.
03087     if (CFP->getValueAPF().isNaN()) {
03088       if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
03089         return ConstantInt::getFalse(CFP->getContext());
03090       assert(FCmpInst::isUnordered(Pred) &&
03091              "Comparison must be either ordered or unordered!");
03092       // True if unordered.
03093       return ConstantInt::getTrue(CFP->getContext());
03094     }
03095     // Check whether the constant is an infinity.
03096     if (CFP->getValueAPF().isInfinity()) {
03097       if (CFP->getValueAPF().isNegative()) {
03098         switch (Pred) {
03099         case FCmpInst::FCMP_OLT:
03100           // No value is ordered and less than negative infinity.
03101           return ConstantInt::getFalse(CFP->getContext());
03102         case FCmpInst::FCMP_UGE:
03103           // All values are unordered with or at least negative infinity.
03104           return ConstantInt::getTrue(CFP->getContext());
03105         default:
03106           break;
03107         }
03108       } else {
03109         switch (Pred) {
03110         case FCmpInst::FCMP_OGT:
03111           // No value is ordered and greater than infinity.
03112           return ConstantInt::getFalse(CFP->getContext());
03113         case FCmpInst::FCMP_ULE:
03114           // All values are unordered with and at most infinity.
03115           return ConstantInt::getTrue(CFP->getContext());
03116         default:
03117           break;
03118         }
03119       }
03120     }
03121     if (CFP->getValueAPF().isZero()) {
03122       switch (Pred) {
03123       case FCmpInst::FCMP_UGE:
03124         if (CannotBeOrderedLessThanZero(LHS))
03125           return ConstantInt::getTrue(CFP->getContext());
03126         break;
03127       case FCmpInst::FCMP_OLT:
03128         // X < 0
03129         if (CannotBeOrderedLessThanZero(LHS))
03130           return ConstantInt::getFalse(CFP->getContext());
03131         break;
03132       default:
03133         break;
03134       }
03135     }
03136   }
03137 
03138   // If the comparison is with the result of a select instruction, check whether
03139   // comparing with either branch of the select always yields the same value.
03140   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
03141     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
03142       return V;
03143 
03144   // If the comparison is with the result of a phi instruction, check whether
03145   // doing the compare with each incoming phi value yields a common result.
03146   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
03147     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
03148       return V;
03149 
03150   return nullptr;
03151 }
03152 
03153 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
03154                               const DataLayout &DL,
03155                               const TargetLibraryInfo *TLI,
03156                               const DominatorTree *DT, AssumptionCache *AC,
03157                               const Instruction *CxtI) {
03158   return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI),
03159                             RecursionLimit);
03160 }
03161 
03162 /// SimplifyWithOpReplaced - See if V simplifies when its operand Op is
03163 /// replaced with RepOp.
03164 static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
03165                                            const Query &Q,
03166                                            unsigned MaxRecurse) {
03167   // Trivial replacement.
03168   if (V == Op)
03169     return RepOp;
03170 
03171   auto *I = dyn_cast<Instruction>(V);
03172   if (!I)
03173     return nullptr;
03174 
03175   // If this is a binary operator, try to simplify it with the replaced op.
03176   if (auto *B = dyn_cast<BinaryOperator>(I)) {
03177     // Consider:
03178     //   %cmp = icmp eq i32 %x, 2147483647
03179     //   %add = add nsw i32 %x, 1
03180     //   %sel = select i1 %cmp, i32 -2147483648, i32 %add
03181     //
03182     // We can't replace %sel with %add unless we strip away the flags.
03183     if (isa<OverflowingBinaryOperator>(B))
03184       if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap())
03185         return nullptr;
03186     if (isa<PossiblyExactOperator>(B))
03187       if (B->isExact())
03188         return nullptr;
03189 
03190     if (MaxRecurse) {
03191       if (B->getOperand(0) == Op)
03192         return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q,
03193                              MaxRecurse - 1);
03194       if (B->getOperand(1) == Op)
03195         return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q,
03196                              MaxRecurse - 1);
03197     }
03198   }
03199 
03200   // Same for CmpInsts.
03201   if (CmpInst *C = dyn_cast<CmpInst>(I)) {
03202     if (MaxRecurse) {
03203       if (C->getOperand(0) == Op)
03204         return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q,
03205                                MaxRecurse - 1);
03206       if (C->getOperand(1) == Op)
03207         return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q,
03208                                MaxRecurse - 1);
03209     }
03210   }
03211 
03212   // TODO: We could hand off more cases to instsimplify here.
03213 
03214   // If all operands are constant after substituting Op for RepOp then we can
03215   // constant fold the instruction.
03216   if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
03217     // Build a list of all constant operands.
03218     SmallVector<Constant *, 8> ConstOps;
03219     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
03220       if (I->getOperand(i) == Op)
03221         ConstOps.push_back(CRepOp);
03222       else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i)))
03223         ConstOps.push_back(COp);
03224       else
03225         break;
03226     }
03227 
03228     // All operands were constants, fold it.
03229     if (ConstOps.size() == I->getNumOperands()) {
03230       if (CmpInst *C = dyn_cast<CmpInst>(I))
03231         return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
03232                                                ConstOps[1], Q.DL, Q.TLI);
03233 
03234       if (LoadInst *LI = dyn_cast<LoadInst>(I))
03235         if (!LI->isVolatile())
03236           return ConstantFoldLoadFromConstPtr(ConstOps[0], Q.DL);
03237 
03238       return ConstantFoldInstOperands(I->getOpcode(), I->getType(), ConstOps,
03239                                       Q.DL, Q.TLI);
03240     }
03241   }
03242 
03243   return nullptr;
03244 }
03245 
03246 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
03247 /// the result.  If not, this returns null.
03248 static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal,
03249                                  Value *FalseVal, const Query &Q,
03250                                  unsigned MaxRecurse) {
03251   // select true, X, Y  -> X
03252   // select false, X, Y -> Y
03253   if (Constant *CB = dyn_cast<Constant>(CondVal)) {
03254     if (CB->isAllOnesValue())
03255       return TrueVal;
03256     if (CB->isNullValue())
03257       return FalseVal;
03258   }
03259 
03260   // select C, X, X -> X
03261   if (TrueVal == FalseVal)
03262     return TrueVal;
03263 
03264   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
03265     if (isa<Constant>(TrueVal))
03266       return TrueVal;
03267     return FalseVal;
03268   }
03269   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
03270     return FalseVal;
03271   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
03272     return TrueVal;
03273 
03274   if (const auto *ICI = dyn_cast<ICmpInst>(CondVal)) {
03275     unsigned BitWidth = Q.DL.getTypeSizeInBits(TrueVal->getType());
03276     ICmpInst::Predicate Pred = ICI->getPredicate();
03277     Value *CmpLHS = ICI->getOperand(0);
03278     Value *CmpRHS = ICI->getOperand(1);
03279     APInt MinSignedValue = APInt::getSignBit(BitWidth);
03280     Value *X;
03281     const APInt *Y;
03282     bool TrueWhenUnset;
03283     bool IsBitTest = false;
03284     if (ICmpInst::isEquality(Pred) &&
03285         match(CmpLHS, m_And(m_Value(X), m_APInt(Y))) &&
03286         match(CmpRHS, m_Zero())) {
03287       IsBitTest = true;
03288       TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
03289     } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
03290       X = CmpLHS;
03291       Y = &MinSignedValue;
03292       IsBitTest = true;
03293       TrueWhenUnset = false;
03294     } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
03295       X = CmpLHS;
03296       Y = &MinSignedValue;
03297       IsBitTest = true;
03298       TrueWhenUnset = true;
03299     }
03300     if (IsBitTest) {
03301       const APInt *C;
03302       // (X & Y) == 0 ? X & ~Y : X  --> X
03303       // (X & Y) != 0 ? X & ~Y : X  --> X & ~Y
03304       if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) &&
03305           *Y == ~*C)
03306         return TrueWhenUnset ? FalseVal : TrueVal;
03307       // (X & Y) == 0 ? X : X & ~Y  --> X & ~Y
03308       // (X & Y) != 0 ? X : X & ~Y  --> X
03309       if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) &&
03310           *Y == ~*C)
03311         return TrueWhenUnset ? FalseVal : TrueVal;
03312 
03313       if (Y->isPowerOf2()) {
03314         // (X & Y) == 0 ? X | Y : X  --> X | Y
03315         // (X & Y) != 0 ? X | Y : X  --> X
03316         if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) &&
03317             *Y == *C)
03318           return TrueWhenUnset ? TrueVal : FalseVal;
03319         // (X & Y) == 0 ? X : X | Y  --> X
03320         // (X & Y) != 0 ? X : X | Y  --> X | Y
03321         if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
03322             *Y == *C)
03323           return TrueWhenUnset ? TrueVal : FalseVal;
03324       }
03325     }
03326     if (ICI->hasOneUse()) {
03327       const APInt *C;
03328       if (match(CmpRHS, m_APInt(C))) {
03329         // X < MIN ? T : F  -->  F
03330         if (Pred == ICmpInst::ICMP_SLT && C->isMinSignedValue())
03331           return FalseVal;
03332         // X < MIN ? T : F  -->  F
03333         if (Pred == ICmpInst::ICMP_ULT && C->isMinValue())
03334           return FalseVal;
03335         // X > MAX ? T : F  -->  F
03336         if (Pred == ICmpInst::ICMP_SGT && C->isMaxSignedValue())
03337           return FalseVal;
03338         // X > MAX ? T : F  -->  F
03339         if (Pred == ICmpInst::ICMP_UGT && C->isMaxValue())
03340           return FalseVal;
03341       }
03342     }
03343 
03344     // If we have an equality comparison then we know the value in one of the
03345     // arms of the select. See if substituting this value into the arm and
03346     // simplifying the result yields the same value as the other arm.
03347     if (Pred == ICmpInst::ICMP_EQ) {
03348       if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
03349               TrueVal ||
03350           SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
03351               TrueVal)
03352         return FalseVal;
03353       if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
03354               FalseVal ||
03355           SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
03356               FalseVal)
03357         return FalseVal;
03358     } else if (Pred == ICmpInst::ICMP_NE) {
03359       if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
03360               FalseVal ||
03361           SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
03362               FalseVal)
03363         return TrueVal;
03364       if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
03365               TrueVal ||
03366           SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
03367               TrueVal)
03368         return TrueVal;
03369     }
03370   }
03371 
03372   return nullptr;
03373 }
03374 
03375 Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
03376                                 const DataLayout &DL,
03377                                 const TargetLibraryInfo *TLI,
03378                                 const DominatorTree *DT, AssumptionCache *AC,
03379                                 const Instruction *CxtI) {
03380   return ::SimplifySelectInst(Cond, TrueVal, FalseVal,
03381                               Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
03382 }
03383 
03384 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
03385 /// fold the result.  If not, this returns null.
03386 static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
03387                               const Query &Q, unsigned) {
03388   // The type of the GEP pointer operand.
03389   unsigned AS =
03390       cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace();
03391 
03392   // getelementptr P -> P.
03393   if (Ops.size() == 1)
03394     return Ops[0];
03395 
03396   // Compute the (pointer) type returned by the GEP instruction.
03397   Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1));
03398   Type *GEPTy = PointerType::get(LastType, AS);
03399   if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
03400     GEPTy = VectorType::get(GEPTy, VT->getNumElements());
03401 
03402   if (isa<UndefValue>(Ops[0]))
03403     return UndefValue::get(GEPTy);
03404 
03405   if (Ops.size() == 2) {
03406     // getelementptr P, 0 -> P.
03407     if (match(Ops[1], m_Zero()))
03408       return Ops[0];
03409 
03410     Type *Ty = SrcTy;
03411     if (Ty->isSized()) {
03412       Value *P;
03413       uint64_t C;
03414       uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty);
03415       // getelementptr P, N -> P if P points to a type of zero size.
03416       if (TyAllocSize == 0)
03417         return Ops[0];
03418 
03419       // The following transforms are only safe if the ptrtoint cast
03420       // doesn't truncate the pointers.
03421       if (Ops[1]->getType()->getScalarSizeInBits() ==
03422           Q.DL.getPointerSizeInBits(AS)) {
03423         auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * {
03424           if (match(P, m_Zero()))
03425             return Constant::getNullValue(GEPTy);
03426           Value *Temp;
03427           if (match(P, m_PtrToInt(m_Value(Temp))))
03428             if (Temp->getType() == GEPTy)
03429               return Temp;
03430           return nullptr;
03431         };
03432 
03433         // getelementptr V, (sub P, V) -> P if P points to a type of size 1.
03434         if (TyAllocSize == 1 &&
03435             match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0])))))
03436           if (Value *R = PtrToIntOrZero(P))
03437             return R;
03438 
03439         // getelementptr V, (ashr (sub P, V), C) -> Q
03440         // if P points to a type of size 1 << C.
03441         if (match(Ops[1],
03442                   m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
03443                          m_ConstantInt(C))) &&
03444             TyAllocSize == 1ULL << C)
03445           if (Value *R = PtrToIntOrZero(P))
03446             return R;
03447 
03448         // getelementptr V, (sdiv (sub P, V), C) -> Q
03449         // if P points to a type of size C.
03450         if (match(Ops[1],
03451                   m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
03452                          m_SpecificInt(TyAllocSize))))
03453           if (Value *R = PtrToIntOrZero(P))
03454             return R;
03455       }
03456     }
03457   }
03458 
03459   // Check to see if this is constant foldable.
03460   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
03461     if (!isa<Constant>(Ops[i]))
03462       return nullptr;
03463 
03464   return ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]),
03465                                         Ops.slice(1));
03466 }
03467 
03468 Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout &DL,
03469                              const TargetLibraryInfo *TLI,
03470                              const DominatorTree *DT, AssumptionCache *AC,
03471                              const Instruction *CxtI) {
03472   return ::SimplifyGEPInst(
03473       cast<PointerType>(Ops[0]->getType()->getScalarType())->getElementType(),
03474       Ops, Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
03475 }
03476 
03477 /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
03478 /// can fold the result.  If not, this returns null.
03479 static Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
03480                                       ArrayRef<unsigned> Idxs, const Query &Q,
03481                                       unsigned) {
03482   if (Constant *CAgg = dyn_cast<Constant>(Agg))
03483     if (Constant *CVal = dyn_cast<Constant>(Val))
03484       return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
03485 
03486   // insertvalue x, undef, n -> x
03487   if (match(Val, m_Undef()))
03488     return Agg;
03489 
03490   // insertvalue x, (extractvalue y, n), n
03491   if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
03492     if (EV->getAggregateOperand()->getType() == Agg->getType() &&
03493         EV->getIndices() == Idxs) {
03494       // insertvalue undef, (extractvalue y, n), n -> y
03495       if (match(Agg, m_Undef()))
03496         return EV->getAggregateOperand();
03497 
03498       // insertvalue y, (extractvalue y, n), n -> y
03499       if (Agg == EV->getAggregateOperand())
03500         return Agg;
03501     }
03502 
03503   return nullptr;
03504 }
03505 
03506 Value *llvm::SimplifyInsertValueInst(
03507     Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout &DL,
03508     const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC,
03509     const Instruction *CxtI) {
03510   return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query(DL, TLI, DT, AC, CxtI),
03511                                    RecursionLimit);
03512 }
03513 
03514 /// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
03515 static Value *SimplifyPHINode(PHINode *PN, const Query &Q) {
03516   // If all of the PHI's incoming values are the same then replace the PHI node
03517   // with the common value.
03518   Value *CommonValue = nullptr;
03519   bool HasUndefInput = false;
03520   for (Value *Incoming : PN->incoming_values()) {
03521     // If the incoming value is the phi node itself, it can safely be skipped.
03522     if (Incoming == PN) continue;
03523     if (isa<UndefValue>(Incoming)) {
03524       // Remember that we saw an undef value, but otherwise ignore them.
03525       HasUndefInput = true;
03526       continue;
03527     }
03528     if (CommonValue && Incoming != CommonValue)
03529       return nullptr;  // Not the same, bail out.
03530     CommonValue = Incoming;
03531   }
03532 
03533   // If CommonValue is null then all of the incoming values were either undef or
03534   // equal to the phi node itself.
03535   if (!CommonValue)
03536     return UndefValue::get(PN->getType());
03537 
03538   // If we have a PHI node like phi(X, undef, X), where X is defined by some
03539   // instruction, we cannot return X as the result of the PHI node unless it
03540   // dominates the PHI block.
03541   if (HasUndefInput)
03542     return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr;
03543 
03544   return CommonValue;
03545 }
03546 
03547 static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) {
03548   if (Constant *C = dyn_cast<Constant>(Op))
03549     return ConstantFoldInstOperands(Instruction::Trunc, Ty, C, Q.DL, Q.TLI);
03550 
03551   return nullptr;
03552 }
03553 
03554 Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout &DL,
03555                                const TargetLibraryInfo *TLI,
03556                                const DominatorTree *DT, AssumptionCache *AC,
03557                                const Instruction *CxtI) {
03558   return ::SimplifyTruncInst(Op, Ty, Query(DL, TLI, DT, AC, CxtI),
03559                              RecursionLimit);
03560 }
03561 
03562 //=== Helper functions for higher up the class hierarchy.
03563 
03564 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
03565 /// fold the result.  If not, this returns null.
03566 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
03567                             const Query &Q, unsigned MaxRecurse) {
03568   switch (Opcode) {
03569   case Instruction::Add:
03570     return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
03571                            Q, MaxRecurse);
03572   case Instruction::FAdd:
03573     return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
03574 
03575   case Instruction::Sub:
03576     return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
03577                            Q, MaxRecurse);
03578   case Instruction::FSub:
03579     return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
03580 
03581   case Instruction::Mul:  return SimplifyMulInst (LHS, RHS, Q, MaxRecurse);
03582   case Instruction::FMul:
03583     return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse);
03584   case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse);
03585   case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse);
03586   case Instruction::FDiv:
03587       return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
03588   case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse);
03589   case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse);
03590   case Instruction::FRem:
03591       return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
03592   case Instruction::Shl:
03593     return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
03594                            Q, MaxRecurse);
03595   case Instruction::LShr:
03596     return SimplifyLShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse);
03597   case Instruction::AShr:
03598     return SimplifyAShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse);
03599   case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse);
03600   case Instruction::Or:  return SimplifyOrInst (LHS, RHS, Q, MaxRecurse);
03601   case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse);
03602   default:
03603     if (Constant *CLHS = dyn_cast<Constant>(LHS))
03604       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
03605         Constant *COps[] = {CLHS, CRHS};
03606         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, Q.DL,
03607                                         Q.TLI);
03608       }
03609 
03610     // If the operation is associative, try some generic simplifications.
03611     if (Instruction::isAssociative(Opcode))
03612       if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, Q, MaxRecurse))
03613         return V;
03614 
03615     // If the operation is with the result of a select instruction check whether
03616     // operating on either branch of the select always yields the same value.
03617     if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
03618       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, Q, MaxRecurse))
03619         return V;
03620 
03621     // If the operation is with the result of a phi instruction, check whether
03622     // operating on all incoming values of the phi always yields the same value.
03623     if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
03624       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, Q, MaxRecurse))
03625         return V;
03626 
03627     return nullptr;
03628   }
03629 }
03630 
03631 /// SimplifyFPBinOp - Given operands for a BinaryOperator, see if we can
03632 /// fold the result.  If not, this returns null.
03633 /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
03634 /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
03635 static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
03636                               const FastMathFlags &FMF, const Query &Q,
03637                               unsigned MaxRecurse) {
03638   switch (Opcode) {
03639   case Instruction::FAdd:
03640     return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse);
03641   case Instruction::FSub:
03642     return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse);
03643   case Instruction::FMul:
03644     return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse);
03645   default:
03646     return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse);
03647   }
03648 }
03649 
03650 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
03651                            const DataLayout &DL, const TargetLibraryInfo *TLI,
03652                            const DominatorTree *DT, AssumptionCache *AC,
03653                            const Instruction *CxtI) {
03654   return ::SimplifyBinOp(Opcode, LHS, RHS, Query(DL, TLI, DT, AC, CxtI),
03655                          RecursionLimit);
03656 }
03657 
03658 Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
03659                              const FastMathFlags &FMF, const DataLayout &DL,
03660                              const TargetLibraryInfo *TLI,
03661                              const DominatorTree *DT, AssumptionCache *AC,
03662                              const Instruction *CxtI) {
03663   return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Query(DL, TLI, DT, AC, CxtI),
03664                            RecursionLimit);
03665 }
03666 
03667 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
03668 /// fold the result.
03669 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
03670                               const Query &Q, unsigned MaxRecurse) {
03671   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
03672     return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
03673   return SimplifyFCmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
03674 }
03675 
03676 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
03677                              const DataLayout &DL, const TargetLibraryInfo *TLI,
03678                              const DominatorTree *DT, AssumptionCache *AC,
03679                              const Instruction *CxtI) {
03680   return ::SimplifyCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI),
03681                            RecursionLimit);
03682 }
03683 
03684 static bool IsIdempotent(Intrinsic::ID ID) {
03685   switch (ID) {
03686   default: return false;
03687 
03688   // Unary idempotent: f(f(x)) = f(x)
03689   case Intrinsic::fabs:
03690   case Intrinsic::floor:
03691   case Intrinsic::ceil:
03692   case Intrinsic::trunc:
03693   case Intrinsic::rint:
03694   case Intrinsic::nearbyint:
03695   case Intrinsic::round:
03696     return true;
03697   }
03698 }
03699 
03700 template <typename IterTy>
03701 static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd,
03702                                 const Query &Q, unsigned MaxRecurse) {
03703   Intrinsic::ID IID = F->getIntrinsicID();
03704   unsigned NumOperands = std::distance(ArgBegin, ArgEnd);
03705   Type *ReturnType = F->getReturnType();
03706 
03707   // Binary Ops
03708   if (NumOperands == 2) {
03709     Value *LHS = *ArgBegin;
03710     Value *RHS = *(ArgBegin + 1);
03711     if (IID == Intrinsic::usub_with_overflow ||
03712         IID == Intrinsic::ssub_with_overflow) {
03713       // X - X -> { 0, false }
03714       if (LHS == RHS)
03715         return Constant::getNullValue(ReturnType);
03716 
03717       // X - undef -> undef
03718       // undef - X -> undef
03719       if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
03720         return UndefValue::get(ReturnType);
03721     }
03722 
03723     if (IID == Intrinsic::uadd_with_overflow ||
03724         IID == Intrinsic::sadd_with_overflow) {
03725       // X + undef -> undef
03726       if (isa<UndefValue>(RHS))
03727         return UndefValue::get(ReturnType);
03728     }
03729 
03730     if (IID == Intrinsic::umul_with_overflow ||
03731         IID == Intrinsic::smul_with_overflow) {
03732       // X * 0 -> { 0, false }
03733       if (match(RHS, m_Zero()))
03734         return Constant::getNullValue(ReturnType);
03735 
03736       // X * undef -> { 0, false }
03737       if (match(RHS, m_Undef()))
03738         return Constant::getNullValue(ReturnType);
03739     }
03740   }
03741 
03742   // Perform idempotent optimizations
03743   if (!IsIdempotent(IID))
03744     return nullptr;
03745 
03746   // Unary Ops
03747   if (NumOperands == 1)
03748     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin))
03749       if (II->getIntrinsicID() == IID)
03750         return II;
03751 
03752   return nullptr;
03753 }
03754 
03755 template <typename IterTy>
03756 static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd,
03757                            const Query &Q, unsigned MaxRecurse) {
03758   Type *Ty = V->getType();
03759   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
03760     Ty = PTy->getElementType();
03761   FunctionType *FTy = cast<FunctionType>(Ty);
03762 
03763   // call undef -> undef
03764   if (isa<UndefValue>(V))
03765     return UndefValue::get(FTy->getReturnType());
03766 
03767   Function *F = dyn_cast<Function>(V);
03768   if (!F)
03769     return nullptr;
03770 
03771   if (F->isIntrinsic())
03772     if (Value *Ret = SimplifyIntrinsic(F, ArgBegin, ArgEnd, Q, MaxRecurse))
03773       return Ret;
03774 
03775   if (!canConstantFoldCallTo(F))
03776     return nullptr;
03777 
03778   SmallVector<Constant *, 4> ConstantArgs;
03779   ConstantArgs.reserve(ArgEnd - ArgBegin);
03780   for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) {
03781     Constant *C = dyn_cast<Constant>(*I);
03782     if (!C)
03783       return nullptr;
03784     ConstantArgs.push_back(C);
03785   }
03786 
03787   return ConstantFoldCall(F, ConstantArgs, Q.TLI);
03788 }
03789 
03790 Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin,
03791                           User::op_iterator ArgEnd, const DataLayout &DL,
03792                           const TargetLibraryInfo *TLI, const DominatorTree *DT,
03793                           AssumptionCache *AC, const Instruction *CxtI) {
03794   return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT, AC, CxtI),
03795                         RecursionLimit);
03796 }
03797 
03798 Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args,
03799                           const DataLayout &DL, const TargetLibraryInfo *TLI,
03800                           const DominatorTree *DT, AssumptionCache *AC,
03801                           const Instruction *CxtI) {
03802   return ::SimplifyCall(V, Args.begin(), Args.end(),
03803                         Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
03804 }
03805 
03806 /// SimplifyInstruction - See if we can compute a simplified version of this
03807 /// instruction.  If not, this returns null.
03808 Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL,
03809                                  const TargetLibraryInfo *TLI,
03810                                  const DominatorTree *DT, AssumptionCache *AC) {
03811   Value *Result;
03812 
03813   switch (I->getOpcode()) {
03814   default:
03815     Result = ConstantFoldInstruction(I, DL, TLI);
03816     break;
03817   case Instruction::FAdd:
03818     Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1),
03819                               I->getFastMathFlags(), DL, TLI, DT, AC, I);
03820     break;
03821   case Instruction::Add:
03822     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
03823                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
03824                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL,
03825                              TLI, DT, AC, I);
03826     break;
03827   case Instruction::FSub:
03828     Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1),
03829                               I->getFastMathFlags(), DL, TLI, DT, AC, I);
03830     break;
03831   case Instruction::Sub:
03832     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
03833                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
03834                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL,
03835                              TLI, DT, AC, I);
03836     break;
03837   case Instruction::FMul:
03838     Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1),
03839                               I->getFastMathFlags(), DL, TLI, DT, AC, I);
03840     break;
03841   case Instruction::Mul:
03842     Result =
03843         SimplifyMulInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
03844     break;
03845   case Instruction::SDiv:
03846     Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
03847                               AC, I);
03848     break;
03849   case Instruction::UDiv:
03850     Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
03851                               AC, I);
03852     break;
03853   case Instruction::FDiv:
03854     Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1),
03855                               I->getFastMathFlags(), DL, TLI, DT, AC, I);
03856     break;
03857   case Instruction::SRem:
03858     Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
03859                               AC, I);
03860     break;
03861   case Instruction::URem:
03862     Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
03863                               AC, I);
03864     break;
03865   case Instruction::FRem:
03866     Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1),
03867                               I->getFastMathFlags(), DL, TLI, DT, AC, I);
03868     break;
03869   case Instruction::Shl:
03870     Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
03871                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
03872                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL,
03873                              TLI, DT, AC, I);
03874     break;
03875   case Instruction::LShr:
03876     Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
03877                               cast<BinaryOperator>(I)->isExact(), DL, TLI, DT,
03878                               AC, I);
03879     break;
03880   case Instruction::AShr:
03881     Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
03882                               cast<BinaryOperator>(I)->isExact(), DL, TLI, DT,
03883                               AC, I);
03884     break;
03885   case Instruction::And:
03886     Result =
03887         SimplifyAndInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
03888     break;
03889   case Instruction::Or:
03890     Result =
03891         SimplifyOrInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
03892     break;
03893   case Instruction::Xor:
03894     Result =
03895         SimplifyXorInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
03896     break;
03897   case Instruction::ICmp:
03898     Result =
03899         SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), I->getOperand(0),
03900                          I->getOperand(1), DL, TLI, DT, AC, I);
03901     break;
03902   case Instruction::FCmp:
03903     Result =
03904         SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), I->getOperand(0),
03905                          I->getOperand(1), DL, TLI, DT, AC, I);
03906     break;
03907   case Instruction::Select:
03908     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
03909                                 I->getOperand(2), DL, TLI, DT, AC, I);
03910     break;
03911   case Instruction::GetElementPtr: {
03912     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
03913     Result = SimplifyGEPInst(Ops, DL, TLI, DT, AC, I);
03914     break;
03915   }
03916   case Instruction::InsertValue: {
03917     InsertValueInst *IV = cast<InsertValueInst>(I);
03918     Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
03919                                      IV->getInsertedValueOperand(),
03920                                      IV->getIndices(), DL, TLI, DT, AC, I);
03921     break;
03922   }
03923   case Instruction::PHI:
03924     Result = SimplifyPHINode(cast<PHINode>(I), Query(DL, TLI, DT, AC, I));
03925     break;
03926   case Instruction::Call: {
03927     CallSite CS(cast<CallInst>(I));
03928     Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), DL,
03929                           TLI, DT, AC, I);
03930     break;
03931   }
03932   case Instruction::Trunc:
03933     Result =
03934         SimplifyTruncInst(I->getOperand(0), I->getType(), DL, TLI, DT, AC, I);
03935     break;
03936   }
03937 
03938   /// If called on unreachable code, the above logic may report that the
03939   /// instruction simplified to itself.  Make life easier for users by
03940   /// detecting that case here, returning a safe value instead.
03941   return Result == I ? UndefValue::get(I->getType()) : Result;
03942 }
03943 
03944 /// \brief Implementation of recursive simplification through an instructions
03945 /// uses.
03946 ///
03947 /// This is the common implementation of the recursive simplification routines.
03948 /// If we have a pre-simplified value in 'SimpleV', that is forcibly used to
03949 /// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of
03950 /// instructions to process and attempt to simplify it using
03951 /// InstructionSimplify.
03952 ///
03953 /// This routine returns 'true' only when *it* simplifies something. The passed
03954 /// in simplified value does not count toward this.
03955 static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
03956                                               const TargetLibraryInfo *TLI,
03957                                               const DominatorTree *DT,
03958                                               AssumptionCache *AC) {
03959   bool Simplified = false;
03960   SmallSetVector<Instruction *, 8> Worklist;
03961   const DataLayout &DL = I->getModule()->getDataLayout();
03962 
03963   // If we have an explicit value to collapse to, do that round of the
03964   // simplification loop by hand initially.
03965   if (SimpleV) {
03966     for (User *U : I->users())
03967       if (U != I)
03968         Worklist.insert(cast<Instruction>(U));
03969 
03970     // Replace the instruction with its simplified value.
03971     I->replaceAllUsesWith(SimpleV);
03972 
03973     // Gracefully handle edge cases where the instruction is not wired into any
03974     // parent block.
03975     if (I->getParent())
03976       I->eraseFromParent();
03977   } else {
03978     Worklist.insert(I);
03979   }
03980 
03981   // Note that we must test the size on each iteration, the worklist can grow.
03982   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
03983     I = Worklist[Idx];
03984 
03985     // See if this instruction simplifies.
03986     SimpleV = SimplifyInstruction(I, DL, TLI, DT, AC);
03987     if (!SimpleV)
03988       continue;
03989 
03990     Simplified = true;
03991 
03992     // Stash away all the uses of the old instruction so we can check them for
03993     // recursive simplifications after a RAUW. This is cheaper than checking all
03994     // uses of To on the recursive step in most cases.
03995     for (User *U : I->users())
03996       Worklist.insert(cast<Instruction>(U));
03997 
03998     // Replace the instruction with its simplified value.
03999     I->replaceAllUsesWith(SimpleV);
04000 
04001     // Gracefully handle edge cases where the instruction is not wired into any
04002     // parent block.
04003     if (I->getParent())
04004       I->eraseFromParent();
04005   }
04006   return Simplified;
04007 }
04008 
04009 bool llvm::recursivelySimplifyInstruction(Instruction *I,
04010                                           const TargetLibraryInfo *TLI,
04011                                           const DominatorTree *DT,
04012                                           AssumptionCache *AC) {
04013   return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC);
04014 }
04015 
04016 bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
04017                                          const TargetLibraryInfo *TLI,
04018                                          const DominatorTree *DT,
04019                                          AssumptionCache *AC) {
04020   assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!");
04021   assert(SimpleV && "Must provide a simplified value.");
04022   return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC);
04023 }