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