LLVM API Documentation

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