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