LCOV - code coverage report
Current view: top level - lib/Analysis - InstructionSimplify.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1995 2052 97.2 %
Date: 2017-09-14 15:23:50 Functions: 115 119 96.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements routines for folding instructions into simpler forms
      11             : // that do not require creating new instructions.  This does constant folding
      12             : // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
      13             : // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
      14             : // ("and i32 %x, %x" -> "%x").  All operands are assumed to have already been
      15             : // simplified: This is usually true and assuming it simplifies the logic (if
      16             : // they have not been simplified then results are correct but maybe suboptimal).
      17             : //
      18             : //===----------------------------------------------------------------------===//
      19             : 
      20             : #include "llvm/Analysis/InstructionSimplify.h"
      21             : #include "llvm/ADT/SetVector.h"
      22             : #include "llvm/ADT/Statistic.h"
      23             : #include "llvm/Analysis/AliasAnalysis.h"
      24             : #include "llvm/Analysis/AssumptionCache.h"
      25             : #include "llvm/Analysis/CaptureTracking.h"
      26             : #include "llvm/Analysis/CmpInstAnalysis.h"
      27             : #include "llvm/Analysis/ConstantFolding.h"
      28             : #include "llvm/Analysis/LoopAnalysisManager.h"
      29             : #include "llvm/Analysis/MemoryBuiltins.h"
      30             : #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
      31             : #include "llvm/Analysis/ValueTracking.h"
      32             : #include "llvm/Analysis/VectorUtils.h"
      33             : #include "llvm/IR/ConstantRange.h"
      34             : #include "llvm/IR/DataLayout.h"
      35             : #include "llvm/IR/Dominators.h"
      36             : #include "llvm/IR/GetElementPtrTypeIterator.h"
      37             : #include "llvm/IR/GlobalAlias.h"
      38             : #include "llvm/IR/Operator.h"
      39             : #include "llvm/IR/PatternMatch.h"
      40             : #include "llvm/IR/ValueHandle.h"
      41             : #include "llvm/Support/KnownBits.h"
      42             : #include <algorithm>
      43             : using namespace llvm;
      44             : using namespace llvm::PatternMatch;
      45             : 
      46             : #define DEBUG_TYPE "instsimplify"
      47             : 
      48             : enum { RecursionLimit = 3 };
      49             : 
      50             : STATISTIC(NumExpand,  "Number of expansions");
      51             : STATISTIC(NumReassoc, "Number of reassociations");
      52             : 
      53             : static Value *SimplifyAndInst(Value *, Value *, const SimplifyQuery &, unsigned);
      54             : static Value *SimplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
      55             :                             unsigned);
      56             : static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &,
      57             :                               const SimplifyQuery &, unsigned);
      58             : static Value *SimplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &,
      59             :                               unsigned);
      60             : static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
      61             :                                const SimplifyQuery &Q, unsigned MaxRecurse);
      62             : static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
      63             : static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned);
      64             : static Value *SimplifyCastInst(unsigned, Value *, Type *,
      65             :                                const SimplifyQuery &, unsigned);
      66             : 
      67             : /// For a boolean type or a vector of boolean type, return false or a vector
      68             : /// with every element false.
      69             : static Constant *getFalse(Type *Ty) {
      70        1827 :   return ConstantInt::getFalse(Ty);
      71             : }
      72             : 
      73             : /// For a boolean type or a vector of boolean type, return true or a vector
      74             : /// with every element true.
      75             : static Constant *getTrue(Type *Ty) {
      76        1955 :   return ConstantInt::getTrue(Ty);
      77             : }
      78             : 
      79             : /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
      80        7328 : static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
      81             :                           Value *RHS) {
      82        6152 :   CmpInst *Cmp = dyn_cast<CmpInst>(V);
      83             :   if (!Cmp)
      84             :     return false;
      85        6152 :   CmpInst::Predicate CPred = Cmp->getPredicate();
      86       12304 :   Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
      87        6152 :   if (CPred == Pred && CLHS == LHS && CRHS == RHS)
      88             :     return true;
      89        8127 :   return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
      90        1995 :     CRHS == LHS;
      91             : }
      92             : 
      93             : /// Does the given value dominate the specified phi node?
      94       95584 : static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
      95       34446 :   Instruction *I = dyn_cast<Instruction>(V);
      96             :   if (!I)
      97             :     // Arguments and constants dominate all instructions.
      98             :     return true;
      99             : 
     100             :   // If we are processing instructions (and/or basic blocks) that have not been
     101             :   // fully added to a function, the parent nodes may still be null. Simply
     102             :   // return the conservative answer in these cases.
     103       34446 :   if (!I->getParent() || !P->getParent() || !I->getParent()->getParent())
     104             :     return false;
     105             : 
     106             :   // If we have a DominatorTree then do a precise test.
     107       34002 :   if (DT)
     108       29418 :     return DT->dominates(I, P);
     109             : 
     110             :   // Otherwise, if the instruction is in the entry block and is not an invoke,
     111             :   // then it obviously dominates all phi nodes.
     112        9208 :   if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
     113          40 :       !isa<InvokeInst>(I))
     114             :     return true;
     115             : 
     116             :   return false;
     117             : }
     118             : 
     119             : /// Simplify "A op (B op' C)" by distributing op over op', turning it into
     120             : /// "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
     121             : /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
     122             : /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
     123             : /// Returns the simplified value, or null if no simplification was performed.
     124      288911 : static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
     125             :                           Instruction::BinaryOps OpcodeToExpand,
     126             :                           const SimplifyQuery &Q, unsigned MaxRecurse) {
     127             :   // Recursion is always used, so bail out at once if we already hit the limit.
     128      288911 :   if (!MaxRecurse--)
     129             :     return nullptr;
     130             : 
     131             :   // Check whether the expression has the form "(A op' B) op C".
     132       87950 :   if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
     133       87950 :     if (Op0->getOpcode() == OpcodeToExpand) {
     134             :       // It does!  Try turning it into "(A op C) op' (B op C)".
     135       44012 :       Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
     136             :       // Do "A op C" and "B op C" both simplify?
     137       22006 :       if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
     138        1905 :         if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
     139             :           // They do! Return "L op' R" if it simplifies or is already available.
     140             :           // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
     141         671 :           if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
     142         664 :                                      && L == B && R == A)) {
     143             :             ++NumExpand;
     144             :             return LHS;
     145             :           }
     146             :           // Otherwise return "L op' R" if it simplifies.
     147         664 :           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
     148             :             ++NumExpand;
     149             :             return V;
     150             :           }
     151             :         }
     152             :     }
     153             : 
     154             :   // Check whether the expression has the form "A op (B op' C)".
     155       52906 :   if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
     156       52906 :     if (Op1->getOpcode() == OpcodeToExpand) {
     157             :       // It does!  Try turning it into "(A op B) op' (A op C)".
     158       37284 :       Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
     159             :       // Do "A op B" and "A op C" both simplify?
     160       12428 :       if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
     161         943 :         if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
     162             :           // They do! Return "L op' R" if it simplifies or is already available.
     163             :           // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
     164          24 :           if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
     165          23 :                                      && L == C && R == B)) {
     166             :             ++NumExpand;
     167             :             return RHS;
     168             :           }
     169             :           // Otherwise return "L op' R" if it simplifies.
     170          23 :           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
     171             :             ++NumExpand;
     172             :             return V;
     173             :           }
     174             :         }
     175             :     }
     176             : 
     177             :   return nullptr;
     178             : }
     179             : 
     180             : /// Generic simplifications for associative binary operations.
     181             : /// Returns the simpler value, or null if none was found.
     182     5019410 : static Value *SimplifyAssociativeBinOp(Instruction::BinaryOps Opcode,
     183             :                                        Value *LHS, Value *RHS,
     184             :                                        const SimplifyQuery &Q,
     185             :                                        unsigned MaxRecurse) {
     186             :   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
     187             : 
     188             :   // Recursion is always used, so bail out at once if we already hit the limit.
     189     5019410 :   if (!MaxRecurse--)
     190             :     return nullptr;
     191             : 
     192     4937434 :   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
     193     4937434 :   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
     194             : 
     195             :   // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
     196     5114819 :   if (Op0 && Op0->getOpcode() == Opcode) {
     197       83065 :     Value *A = Op0->getOperand(0);
     198       83065 :     Value *B = Op0->getOperand(1);
     199       83065 :     Value *C = RHS;
     200             : 
     201             :     // Does "B op C" simplify?
     202       83065 :     if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
     203             :       // It does!  Return "A op V" if it simplifies or is already available.
     204             :       // If V equals B then "A op V" is just the LHS.
     205       60377 :       if (V == B) return LHS;
     206             :       // Otherwise return "A op V" if it simplifies.
     207       60221 :       if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
     208             :         ++NumReassoc;
     209             :         return W;
     210             :       }
     211             :     }
     212             :   }
     213             : 
     214             :   // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
     215     5015058 :   if (Op1 && Op1->getOpcode() == Opcode) {
     216       24763 :     Value *A = LHS;
     217       24763 :     Value *B = Op1->getOperand(0);
     218       24763 :     Value *C = Op1->getOperand(1);
     219             : 
     220             :     // Does "A op B" simplify?
     221       24763 :     if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
     222             :       // It does!  Return "V op C" if it simplifies or is already available.
     223             :       // If V equals B then "V op C" is just the RHS.
     224          23 :       if (V == B) return RHS;
     225             :       // Otherwise return "V op C" if it simplifies.
     226           1 :       if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
     227             :         ++NumReassoc;
     228             :         return W;
     229             :       }
     230             :     }
     231             :   }
     232             : 
     233             :   // The remaining transforms require commutativity as well as associativity.
     234     4934502 :   if (!Instruction::isCommutative(Opcode))
     235             :     return nullptr;
     236             : 
     237             :   // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
     238     5108967 :   if (Op0 && Op0->getOpcode() == Opcode) {
     239       80156 :     Value *A = Op0->getOperand(0);
     240       80156 :     Value *B = Op0->getOperand(1);
     241       80156 :     Value *C = RHS;
     242             : 
     243             :     // Does "C op A" simplify?
     244       80156 :     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
     245             :       // It does!  Return "V op B" if it simplifies or is already available.
     246             :       // If V equals A then "V op B" is just the LHS.
     247         104 :       if (V == A) return LHS;
     248             :       // Otherwise return "V op B" if it simplifies.
     249          62 :       if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
     250             :         ++NumReassoc;
     251             :         return W;
     252             :       }
     253             :     }
     254             :   }
     255             : 
     256             :   // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
     257     5014967 :   if (Op1 && Op1->getOpcode() == Opcode) {
     258       24740 :     Value *A = LHS;
     259       24740 :     Value *B = Op1->getOperand(0);
     260       24740 :     Value *C = Op1->getOperand(1);
     261             : 
     262             :     // Does "C op A" simplify?
     263       24740 :     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
     264             :       // It does!  Return "B op V" if it simplifies or is already available.
     265             :       // If V equals C then "B op V" is just the RHS.
     266          74 :       if (V == C) return RHS;
     267             :       // Otherwise return "B op V" if it simplifies.
     268          68 :       if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
     269             :         ++NumReassoc;
     270             :         return W;
     271             :       }
     272             :     }
     273             :   }
     274             : 
     275             :   return nullptr;
     276             : }
     277             : 
     278             : /// In the case of a binary operation with a select instruction as an operand,
     279             : /// try to simplify the binop by seeing whether evaluating it on both branches
     280             : /// of the select results in the same value. Returns the common value if so,
     281             : /// otherwise returns null.
     282        2316 : static Value *ThreadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS,
     283             :                                     Value *RHS, const SimplifyQuery &Q,
     284             :                                     unsigned MaxRecurse) {
     285             :   // Recursion is always used, so bail out at once if we already hit the limit.
     286        2316 :   if (!MaxRecurse--)
     287             :     return nullptr;
     288             : 
     289             :   SelectInst *SI;
     290        2188 :   if (isa<SelectInst>(LHS)) {
     291             :     SI = cast<SelectInst>(LHS);
     292             :   } else {
     293             :     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
     294             :     SI = cast<SelectInst>(RHS);
     295             :   }
     296             : 
     297             :   // Evaluate the BinOp on the true and false branches of the select.
     298             :   Value *TV;
     299             :   Value *FV;
     300        2188 :   if (SI == LHS) {
     301        1761 :     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
     302        1761 :     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
     303             :   } else {
     304         427 :     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
     305         427 :     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
     306             :   }
     307             : 
     308             :   // If they simplified to the same value, then return the common value.
     309             :   // If they both failed to simplify then return null.
     310        2188 :   if (TV == FV)
     311             :     return TV;
     312             : 
     313             :   // If one branch simplified to undef, return the other one.
     314        2393 :   if (TV && isa<UndefValue>(TV))
     315             :     return FV;
     316        2607 :   if (FV && isa<UndefValue>(FV))
     317             :     return TV;
     318             : 
     319             :   // If applying the operation did not change the true and false select values,
     320             :   // then the result of the binop is the select itself.
     321        1592 :   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
     322             :     return SI;
     323             : 
     324             :   // If one branch simplified and the other did not, and the simplified
     325             :   // value is equal to the unsimplified one, return the simplified value.
     326             :   // For example, select (cond, X, X & Z) & Z -> X & Z.
     327        1582 :   if ((FV && !TV) || (TV && !FV)) {
     328             :     // Check that the simplified value has the form "X op Y" where "op" is the
     329             :     // same as the original operation.
     330        1782 :     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
     331         436 :     if (Simplified && Simplified->getOpcode() == Opcode) {
     332             :       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
     333             :       // We already know that "op" is the same as for the simplified value.  See
     334             :       // if the operands match too.  If so, return the simplified value.
     335          76 :       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
     336          52 :       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
     337          52 :       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
     338         104 :       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
     339           0 :           Simplified->getOperand(1) == UnsimplifiedRHS)
     340             :         return Simplified;
     341         104 :       if (Simplified->isCommutative() &&
     342         104 :           Simplified->getOperand(1) == UnsimplifiedLHS &&
     343           0 :           Simplified->getOperand(0) == UnsimplifiedRHS)
     344             :         return Simplified;
     345             :     }
     346             :   }
     347             : 
     348             :   return nullptr;
     349             : }
     350             : 
     351             : /// In the case of a comparison with a select instruction, try to simplify the
     352             : /// comparison by seeing whether both branches of the select result in the same
     353             : /// value. Returns the common value if so, otherwise returns null.
     354        7734 : static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
     355             :                                   Value *RHS, const SimplifyQuery &Q,
     356             :                                   unsigned MaxRecurse) {
     357             :   // Recursion is always used, so bail out at once if we already hit the limit.
     358        7734 :   if (!MaxRecurse--)
     359             :     return nullptr;
     360             : 
     361             :   // Make sure the select is on the LHS.
     362        7639 :   if (!isa<SelectInst>(LHS)) {
     363        1457 :     std::swap(LHS, RHS);
     364        1457 :     Pred = CmpInst::getSwappedPredicate(Pred);
     365             :   }
     366             :   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
     367       15278 :   SelectInst *SI = cast<SelectInst>(LHS);
     368        7639 :   Value *Cond = SI->getCondition();
     369        7639 :   Value *TV = SI->getTrueValue();
     370        7639 :   Value *FV = SI->getFalseValue();
     371             : 
     372             :   // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
     373             :   // Does "cmp TV, RHS" simplify?
     374        7639 :   Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse);
     375        7639 :   if (TCmp == Cond) {
     376             :     // It not only simplified, it simplified to the select condition.  Replace
     377             :     // it with 'true'.
     378          74 :     TCmp = getTrue(Cond->getType());
     379        7602 :   } else if (!TCmp) {
     380             :     // It didn't simplify.  However if "cmp TV, RHS" is equal to the select
     381             :     // condition then we can replace it with 'true'.  Otherwise give up.
     382        5891 :     if (!isSameCompare(Cond, Pred, TV, RHS))
     383             :       return nullptr;
     384          18 :     TCmp = getTrue(Cond->getType());
     385             :   }
     386             : 
     387             :   // Does "cmp FV, RHS" simplify?
     388        1757 :   Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse);
     389        1757 :   if (FCmp == Cond) {
     390             :     // It not only simplified, it simplified to the select condition.  Replace
     391             :     // it with 'false'.
     392           2 :     FCmp = getFalse(Cond->getType());
     393        1756 :   } else if (!FCmp) {
     394             :     // It didn't simplify.  However if "cmp FV, RHS" is equal to the select
     395             :     // condition then we can replace it with 'false'.  Otherwise give up.
     396        1437 :     if (!isSameCompare(Cond, Pred, FV, RHS))
     397             :       return nullptr;
     398          22 :     FCmp = getFalse(Cond->getType());
     399             :   }
     400             : 
     401             :   // If both sides simplified to the same value, then use it as the result of
     402             :   // the original comparison.
     403         331 :   if (TCmp == FCmp)
     404             :     return TCmp;
     405             : 
     406             :   // The remaining cases only make sense if the select condition has the same
     407             :   // type as the result of the comparison, so bail out if this is not so.
     408         879 :   if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
     409             :     return nullptr;
     410             :   // If the false value simplified to false, then the result of the compare
     411             :   // is equal to "Cond && TCmp".  This also catches the case when the false
     412             :   // value simplified to false and the true value to true, returning "Cond".
     413         575 :   if (match(FCmp, m_Zero()))
     414         131 :     if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse))
     415             :       return V;
     416             :   // If the true value simplified to true, then the result of the compare
     417             :   // is equal to "Cond || FCmp".
     418         322 :   if (match(TCmp, m_One()))
     419           4 :     if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse))
     420             :       return V;
     421             :   // Finally, if the false value simplified to true and the true value to
     422             :   // false, then the result of the compare is equal to "!Cond".
     423         465 :   if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
     424         152 :     if (Value *V =
     425         152 :         SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
     426         152 :                         Q, MaxRecurse))
     427             :       return V;
     428             : 
     429             :   return nullptr;
     430             : }
     431             : 
     432             : /// In the case of a binary operation with an operand that is a PHI instruction,
     433             : /// try to simplify the binop by seeing whether evaluating it on the incoming
     434             : /// phi values yields the same result for every value. If so returns the common
     435             : /// value, otherwise returns null.
     436       34748 : static Value *ThreadBinOpOverPHI(Instruction::BinaryOps Opcode, Value *LHS,
     437             :                                  Value *RHS, const SimplifyQuery &Q,
     438             :                                  unsigned MaxRecurse) {
     439             :   // Recursion is always used, so bail out at once if we already hit the limit.
     440       34748 :   if (!MaxRecurse--)
     441             :     return nullptr;
     442             : 
     443             :   PHINode *PI;
     444       28483 :   if (isa<PHINode>(LHS)) {
     445       44676 :     PI = cast<PHINode>(LHS);
     446             :     // Bail out if RHS and the phi may be mutually interdependent due to a loop.
     447       22338 :     if (!ValueDominatesPHI(RHS, PI, Q.DT))
     448             :       return nullptr;
     449             :   } else {
     450             :     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
     451        6145 :     PI = cast<PHINode>(RHS);
     452             :     // Bail out if LHS and the phi may be mutually interdependent due to a loop.
     453        6145 :     if (!ValueDominatesPHI(LHS, PI, Q.DT))
     454             :       return nullptr;
     455             :   }
     456             : 
     457             :   // Evaluate the BinOp on the incoming phi values.
     458       19644 :   Value *CommonValue = nullptr;
     459       34507 :   for (Value *Incoming : PI->incoming_values()) {
     460             :     // If the incoming value is the phi node itself, it can safely be skipped.
     461       34496 :     if (Incoming == PI) continue;
     462       34496 :     Value *V = PI == LHS ?
     463             :       SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
     464       34496 :       SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
     465             :     // If the operation failed to simplify, or simplified to a different value
     466             :     // to previously, then give up.
     467       34496 :     if (!V || (CommonValue && V != CommonValue))
     468             :       return nullptr;
     469             :     CommonValue = V;
     470             :   }
     471             : 
     472             :   return CommonValue;
     473             : }
     474             : 
     475             : /// In the case of a comparison with a PHI instruction, try to simplify the
     476             : /// comparison by seeing whether comparing with all of the incoming phi values
     477             : /// yields the same result every time. If so returns the common result,
     478             : /// otherwise returns null.
     479       60887 : static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
     480             :                                const SimplifyQuery &Q, unsigned MaxRecurse) {
     481             :   // Recursion is always used, so bail out at once if we already hit the limit.
     482       60887 :   if (!MaxRecurse--)
     483             :     return nullptr;
     484             : 
     485             :   // Make sure the phi is on the LHS.
     486       60106 :   if (!isa<PHINode>(LHS)) {
     487        6277 :     std::swap(LHS, RHS);
     488        6277 :     Pred = CmpInst::getSwappedPredicate(Pred);
     489             :   }
     490             :   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
     491      120212 :   PHINode *PI = cast<PHINode>(LHS);
     492             : 
     493             :   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
     494       60106 :   if (!ValueDominatesPHI(RHS, PI, Q.DT))
     495             :     return nullptr;
     496             : 
     497             :   // Evaluate the BinOp on the incoming phi values.
     498       47327 :   Value *CommonValue = nullptr;
     499       74532 :   for (Value *Incoming : PI->incoming_values()) {
     500             :     // If the incoming value is the phi node itself, it can safely be skipped.
     501       74169 :     if (Incoming == PI) continue;
     502       74167 :     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
     503             :     // If the operation failed to simplify, or simplified to a different value
     504             :     // to previously, then give up.
     505       74167 :     if (!V || (CommonValue && V != CommonValue))
     506             :       return nullptr;
     507             :     CommonValue = V;
     508             :   }
     509             : 
     510             :   return CommonValue;
     511             : }
     512             : 
     513     5350473 : static Constant *foldOrCommuteConstant(Instruction::BinaryOps Opcode,
     514             :                                        Value *&Op0, Value *&Op1,
     515             :                                        const SimplifyQuery &Q) {
     516     5579768 :   if (auto *CLHS = dyn_cast<Constant>(Op0)) {
     517      350166 :     if (auto *CRHS = dyn_cast<Constant>(Op1))
     518      120871 :       return ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, Q.DL);
     519             : 
     520             :     // Canonicalize the constant to the RHS if this is a commutative operation.
     521       81849 :     if (Instruction::isCommutative(Opcode))
     522             :       std::swap(Op0, Op1);
     523             :   }
     524             :   return nullptr;
     525             : }
     526             : 
     527             : /// Given operands for an Add, see if we can fold the result.
     528             : /// If not, this returns null.
     529     4849536 : static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
     530             :                               const SimplifyQuery &Q, unsigned MaxRecurse) {
     531     4849536 :   if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q))
     532             :     return C;
     533             : 
     534             :   // X + undef -> undef
     535     9524290 :   if (match(Op1, m_Undef()))
     536             :     return Op1;
     537             : 
     538             :   // X + 0 -> X
     539     9431840 :   if (match(Op1, m_Zero()))
     540        5444 :     return Op0;
     541             : 
     542             :   // X + (Y - X) -> Y
     543             :   // (Y - X) + X -> Y
     544             :   // Eg: X + -X -> 0
     545     4756700 :   Value *Y = nullptr;
     546    33296898 :   if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
     547    28540190 :       match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
     548          32 :     return Y;
     549             : 
     550             :   // X + ~X -> -1   since   ~X = -X-1
     551     4756668 :   Type *Ty = Op0->getType();
     552    28540006 :   if (match(Op0, m_Not(m_Specific(Op1))) ||
     553    23783332 :       match(Op1, m_Not(m_Specific(Op0))))
     554           2 :     return Constant::getAllOnesValue(Ty);
     555             : 
     556             :   // add nsw/nuw (xor Y, signmask), signmask --> Y
     557             :   // The no-wrapping add guarantees that the top bit will be set by the add.
     558             :   // Therefore, the xor must be clearing the already set sign bit of Y.
     559     4836930 :   if ((isNSW || isNUW) && match(Op1, m_SignMask()) &&
     560     4756694 :       match(Op0, m_Xor(m_Value(Y), m_SignMask())))
     561           3 :     return Y;
     562             : 
     563             :   /// i1 add -> xor.
     564    14157537 :   if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
     565           9 :     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
     566             :       return V;
     567             : 
     568             :   // Try some generic simplifications for associative operations.
     569     9513316 :   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
     570     4756658 :                                           MaxRecurse))
     571             :     return V;
     572             : 
     573             :   // Threading Add over selects and phi nodes is pointless, so don't bother.
     574             :   // Threading over the select in "A + select(cond, B, C)" means evaluating
     575             :   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
     576             :   // only if B and C are equal.  If B and C are equal then (since we assume
     577             :   // that operands have already been simplified) "select(cond, B, C)" should
     578             :   // have been simplified to the common value of B and C already.  Analysing
     579             :   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
     580             :   // for threading over phi nodes.
     581             : 
     582     4756638 :   return nullptr;
     583             : }
     584             : 
     585     4600855 : Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
     586             :                              const SimplifyQuery &Query) {
     587     4600855 :   return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query, RecursionLimit);
     588             : }
     589             : 
     590             : /// \brief Compute the base pointer and cumulative constant offsets for V.
     591             : ///
     592             : /// This strips all constant offsets off of V, leaving it the base pointer, and
     593             : /// accumulates the total constant offset applied in the returned constant. It
     594             : /// returns 0 if V is not a pointer, and returns the constant '0' if there are
     595             : /// no constant offsets applied.
     596             : ///
     597             : /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't
     598             : /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc.
     599             : /// folding.
     600      845686 : static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V,
     601             :                                                 bool AllowNonInbounds = false) {
     602             :   assert(V->getType()->isPtrOrPtrVectorTy());
     603             : 
     604     1691372 :   Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType();
     605     1691372 :   APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth());
     606             : 
     607             :   // Even though we don't look through PHI nodes, we could be called on an
     608             :   // instruction in an unreachable block, which may be on a cycle.
     609     1691372 :   SmallPtrSet<Value *, 4> Visited;
     610      845686 :   Visited.insert(V);
     611             :   do {
     612      903919 :     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
     613       90502 :       if ((!AllowNonInbounds && !GEP->isInBounds()) ||
     614       29436 :           !GEP->accumulateConstantOffset(DL, Offset))
     615             :         break;
     616       27142 :       V = GEP->getPointerOperand();
     617     1275577 :     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
     618         198 :       V = cast<Operator>(V)->getOperand(0);
     619      841805 :     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
     620           0 :       if (GA->isInterposable())
     621             :         break;
     622           0 :       V = GA->getAliasee();
     623             :     } else {
     624     2525415 :       if (auto CS = CallSite(V))
     625       26972 :         if (Value *RV = CS.getReturnedArgOperand()) {
     626           1 :           V = RV;
     627           1 :           continue;
     628             :         }
     629      841804 :       break;
     630             :     }
     631             :     assert(V->getType()->isPtrOrPtrVectorTy() && "Unexpected operand type!");
     632       27209 :   } while (Visited.insert(V).second);
     633             : 
     634      845686 :   Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset);
     635     1691372 :   if (V->getType()->isVectorTy())
     636           4 :     return ConstantVector::getSplat(V->getType()->getVectorNumElements(),
     637           2 :                                     OffsetIntPtr);
     638             :   return OffsetIntPtr;
     639             : }
     640             : 
     641             : /// \brief Compute the constant difference between two pointer values.
     642             : /// If the difference is not a constant, returns zero.
     643       12997 : static Constant *computePointerDifference(const DataLayout &DL, Value *LHS,
     644             :                                           Value *RHS) {
     645       12997 :   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
     646       12997 :   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
     647             : 
     648             :   // If LHS and RHS are not related via constant offsets to the same base
     649             :   // value, there is nothing we can do here.
     650       12997 :   if (LHS != RHS)
     651             :     return nullptr;
     652             : 
     653             :   // Otherwise, the difference of LHS - RHS can be computed as:
     654             :   //    LHS - RHS
     655             :   //  = (LHSOffset + Base) - (RHSOffset + Base)
     656             :   //  = LHSOffset - RHSOffset
     657          10 :   return ConstantExpr::getSub(LHSOffset, RHSOffset);
     658             : }
     659             : 
     660             : /// Given operands for a Sub, see if we can fold the result.
     661             : /// If not, this returns null.
     662       57319 : static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
     663             :                               const SimplifyQuery &Q, unsigned MaxRecurse) {
     664       57319 :   if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q))
     665             :     return C;
     666             : 
     667             :   // X - undef -> undef
     668             :   // undef - X -> undef
     669      168608 :   if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
     670           2 :     return UndefValue::get(Op0->getType());
     671             : 
     672             :   // X - 0 -> X
     673       58675 :   if (match(Op1, m_Zero()))
     674          92 :     return Op0;
     675             : 
     676             :   // X - X -> 0
     677       56109 :   if (Op0 == Op1)
     678         173 :     return Constant::getNullValue(Op0->getType());
     679             : 
     680             :   // Is this a negation?
     681       66326 :   if (match(Op0, m_Zero())) {
     682             :     // 0 - X -> 0 if the sub is NUW.
     683        3436 :     if (isNUW)
     684          11 :       return Op0;
     685             : 
     686        6861 :     KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
     687        3433 :     if (Known.Zero.isMaxSignedValue()) {
     688             :       // Op1 is either 0 or the minimum signed value. If the sub is NSW, then
     689             :       // Op1 must be 0 because negating the minimum signed value is undefined.
     690           5 :       if (isNSW)
     691           7 :         return Op0;
     692             : 
     693             :       // 0 - X -> X if X is 0 or the minimum signed value.
     694           3 :       return Op1;
     695             :     }
     696             :   }
     697             : 
     698             :   // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
     699             :   // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
     700       55928 :   Value *X = nullptr, *Y = nullptr, *Z = Op1;
     701      278748 :   if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
     702             :     // See if "V === Y - Z" simplifies.
     703        2658 :     if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
     704             :       // It does!  Now see if "X + V" simplifies.
     705         235 :       if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
     706             :         // It does, we successfully reassociated!
     707             :         ++NumReassoc;
     708             :         return W;
     709             :       }
     710             :     // See if "V === X - Z" simplifies.
     711        2646 :     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
     712             :       // It does!  Now see if "Y + V" simplifies.
     713          27 :       if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) {
     714             :         // It does, we successfully reassociated!
     715             :         ++NumReassoc;
     716             :         return W;
     717             :       }
     718             :   }
     719             : 
     720             :   // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
     721             :   // For example, X - (X + 1) -> -1
     722       55893 :   X = Op0;
     723      278573 :   if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
     724             :     // See if "V === X - Y" simplifies.
     725         381 :     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
     726             :       // It does!  Now see if "V - Z" simplifies.
     727          45 :       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) {
     728             :         // It does, we successfully reassociated!
     729             :         ++NumReassoc;
     730             :         return W;
     731             :       }
     732             :     // See if "V === X - Z" simplifies.
     733         343 :     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
     734             :       // It does!  Now see if "V - Y" simplifies.
     735         108 :       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) {
     736             :         // It does, we successfully reassociated!
     737             :         ++NumReassoc;
     738             :         return W;
     739             :       }
     740             :   }
     741             : 
     742             :   // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
     743             :   // For example, X - (X - Y) -> Y.
     744       55855 :   Z = Op0;
     745      278383 :   if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
     746             :     // See if "V === Z - X" simplifies.
     747         337 :     if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1))
     748             :       // It does!  Now see if "V + Y" simplifies.
     749          47 :       if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) {
     750             :         // It does, we successfully reassociated!
     751             :         ++NumReassoc;
     752             :         return W;
     753             :       }
     754             : 
     755             :   // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
     756      278597 :   if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
     757       56010 :       match(Op1, m_Trunc(m_Value(Y))))
     758           4 :     if (X->getType() == Y->getType())
     759             :       // See if "V === X - Y" simplifies.
     760           4 :       if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
     761             :         // It does!  Now see if "trunc V" simplifies.
     762           2 :         if (Value *W = SimplifyCastInst(Instruction::Trunc, V, Op0->getType(),
     763           1 :                                         Q, MaxRecurse - 1))
     764             :           // It does, return the simplified "trunc V".
     765             :           return W;
     766             : 
     767             :   // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
     768      238723 :   if (match(Op0, m_PtrToInt(m_Value(X))) &&
     769      101918 :       match(Op1, m_PtrToInt(m_Value(Y))))
     770       12997 :     if (Constant *Result = computePointerDifference(Q.DL, X, Y))
     771          10 :       return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
     772             : 
     773             :   // i1 sub -> xor.
     774      111439 :   if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
     775           6 :     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
     776             :       return V;
     777             : 
     778             :   // Threading Sub over selects and phi nodes is pointless, so don't bother.
     779             :   // Threading over the select in "A - select(cond, B, C)" means evaluating
     780             :   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
     781             :   // only if B and C are equal.  If B and C are equal then (since we assume
     782             :   // that operands have already been simplified) "select(cond, B, C)" should
     783             :   // have been simplified to the common value of B and C already.  Analysing
     784             :   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
     785             :   // for threading over phi nodes.
     786             : 
     787             :   return nullptr;
     788             : }
     789             : 
     790       50141 : Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
     791             :                              const SimplifyQuery &Q) {
     792       50141 :   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
     793             : }
     794             : 
     795             : /// Given operands for a Mul, see if we can fold the result.
     796             : /// If not, this returns null.
     797       70999 : static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
     798             :                               unsigned MaxRecurse) {
     799       70999 :   if (Constant *C = foldOrCommuteConstant(Instruction::Mul, Op0, Op1, Q))
     800             :     return C;
     801             : 
     802             :   // X * undef -> 0
     803      127228 :   if (match(Op1, m_Undef()))
     804           0 :     return Constant::getNullValue(Op0->getType());
     805             : 
     806             :   // X * 0 -> 0
     807       90164 :   if (match(Op1, m_Zero()))
     808         684 :     return Op1;
     809             : 
     810             :   // X * 1 -> X
     811       88796 :   if (match(Op1, m_One()))
     812        2127 :     return Op0;
     813             : 
     814             :   // (X / Y) * Y -> X if the division is exact.
     815       60803 :   Value *X = nullptr;
     816      486188 :   if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
     817      424205 :       match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0)))))   // Y * (X / Y)
     818         238 :     return X;
     819             : 
     820             :   // i1 mul -> and.
     821      140777 :   if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
     822           4 :     if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1))
     823             :       return V;
     824             : 
     825             :   // Try some generic simplifications for associative operations.
     826      121126 :   if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q,
     827       60563 :                                           MaxRecurse))
     828             :     return V;
     829             : 
     830             :   // Mul distributes over Add.  Try some generic simplifications based on this.
     831      121122 :   if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
     832       60561 :                              Q, MaxRecurse))
     833             :     return V;
     834             : 
     835             :   // If the operation is with the result of a select instruction, check whether
     836             :   // operating on either branch of the select always yields the same value.
     837      120660 :   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
     838        1584 :     if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q,
     839         792 :                                          MaxRecurse))
     840             :       return V;
     841             : 
     842             :   // If the operation is with the result of a phi instruction, check whether
     843             :   // operating on all incoming values of the phi always yields the same value.
     844      112473 :   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     845       24700 :     if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q,
     846       12350 :                                       MaxRecurse))
     847             :       return V;
     848             : 
     849             :   return nullptr;
     850             : }
     851             : 
     852       15190 : Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
     853       15190 :   return ::SimplifyMulInst(Op0, Op1, Q, RecursionLimit);
     854             : }
     855             : 
     856             : /// Check for common or similar folds of integer division or integer remainder.
     857             : /// This applies to all 4 opcodes (sdiv/udiv/srem/urem).
     858       16155 : static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv) {
     859       16155 :   Type *Ty = Op0->getType();
     860             : 
     861             :   // X / undef -> undef
     862             :   // X % undef -> undef
     863       32310 :   if (match(Op1, m_Undef()))
     864             :     return Op1;
     865             : 
     866             :   // X / 0 -> undef
     867             :   // X % 0 -> undef
     868             :   // We don't need to preserve faults!
     869       27171 :   if (match(Op1, m_Zero()))
     870          17 :     return UndefValue::get(Ty);
     871             : 
     872             :   // If any element of a constant divisor vector is zero, the whole op is undef.
     873       11002 :   auto *Op1C = dyn_cast<Constant>(Op1);
     874       11002 :   if (Op1C && Ty->isVectorTy()) {
     875         225 :     unsigned NumElts = Ty->getVectorNumElements();
     876        1241 :     for (unsigned i = 0; i != NumElts; ++i) {
     877        1022 :       Constant *Elt = Op1C->getAggregateElement(i);
     878        1022 :       if (Elt && Elt->isNullValue())
     879           6 :         return UndefValue::get(Ty);
     880             :     }
     881             :   }
     882             : 
     883             :   // undef / X -> 0
     884             :   // undef % X -> 0
     885       32258 :   if (match(Op0, m_Undef()))
     886           0 :     return Constant::getNullValue(Ty);
     887             : 
     888             :   // 0 / X -> 0
     889             :   // 0 % X -> 0
     890       17057 :   if (match(Op0, m_Zero()))
     891             :     return Op0;
     892             : 
     893             :   // X / X -> 1
     894             :   // X % X -> 0
     895       16084 :   if (Op0 == Op1)
     896          10 :     return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
     897             : 
     898             :   // X / 1 -> X
     899             :   // X % 1 -> 0
     900             :   // If this is a boolean op (single-bit element type), we can't have
     901             :   // division-by-zero or remainder-by-zero, so assume the divisor is 1.
     902       43110 :   if (match(Op1, m_One()) || Ty->isIntOrIntVectorTy(1))
     903          40 :     return IsDiv ? Op0 : Constant::getNullValue(Ty);
     904             : 
     905             :   return nullptr;
     906             : }
     907             : 
     908             : /// These are simplifications common to SDiv and UDiv.
     909       10037 : static Value *simplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
     910             :                           const SimplifyQuery &Q, unsigned MaxRecurse) {
     911       10037 :   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
     912             :     return C;
     913             : 
     914        9967 :   if (Value *V = simplifyDivRem(Op0, Op1, true))
     915             :     return V;
     916             : 
     917        9897 :   bool isSigned = Opcode == Instruction::SDiv;
     918             : 
     919             :   // (X * Y) / Y -> X if the multiplication does not overflow.
     920        9897 :   Value *X = nullptr, *Y = nullptr;
     921       39588 :   if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
     922          24 :     if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
     923          48 :     OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0);
     924             :     // If the Mul knows it does not overflow, then we are good to go.
     925          46 :     if ((isSigned && Mul->hasNoSignedWrap()) ||
     926           2 :         (!isSigned && Mul->hasNoUnsignedWrap()))
     927           2 :       return X;
     928             :     // If X has the form X = A / Y then X * Y cannot overflow.
     929          44 :     if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X))
     930          34 :       if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y)
     931             :         return X;
     932             :   }
     933             : 
     934             :   // (X rem Y) / Y -> 0
     935       38935 :   if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
     936       23931 :       (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
     937           2 :     return Constant::getNullValue(Op0->getType());
     938             : 
     939             :   // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
     940             :   ConstantInt *C1, *C2;
     941       33818 :   if (!isSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) &&
     942           8 :       match(Op1, m_ConstantInt(C2))) {
     943             :     bool Overflow;
     944           4 :     (void)C1->getValue().umul_ov(C2->getValue(), Overflow);
     945           1 :     if (Overflow)
     946           1 :       return Constant::getNullValue(Op0->getType());
     947             :   }
     948             : 
     949             :   // If the operation is with the result of a select instruction, check whether
     950             :   // operating on either branch of the select always yields the same value.
     951       19766 :   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
     952          29 :     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
     953             :       return V;
     954             : 
     955             :   // If the operation is with the result of a phi instruction, check whether
     956             :   // operating on all incoming values of the phi always yields the same value.
     957       19592 :   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     958         631 :     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
     959             :       return V;
     960             : 
     961             :   return nullptr;
     962             : }
     963             : 
     964             : /// These are simplifications common to SRem and URem.
     965        6839 : static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
     966             :                           const SimplifyQuery &Q, unsigned MaxRecurse) {
     967        6839 :   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
     968             :     return C;
     969             : 
     970        6188 :   if (Value *V = simplifyDivRem(Op0, Op1, false))
     971             :     return V;
     972             : 
     973             :   // (X % Y) % Y -> X % Y
     974         928 :   if ((Opcode == Instruction::SRem &&
     975       21194 :        match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
     976        5209 :       (Opcode == Instruction::URem &&
     977       26973 :        match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
     978           2 :     return Op0;
     979             : 
     980             :   // If the operation is with the result of a select instruction, check whether
     981             :   // operating on either branch of the select always yields the same value.
     982       12236 :   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
     983          81 :     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
     984             :       return V;
     985             : 
     986             :   // If the operation is with the result of a phi instruction, check whether
     987             :   // operating on all incoming values of the phi always yields the same value.
     988       11385 :   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     989         980 :     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
     990             :       return V;
     991             : 
     992             :   return nullptr;
     993             : }
     994             : 
     995             : /// Given a predicate and two operands, return true if the comparison is true.
     996             : /// This is a helper for div/rem simplification where we return some other value
     997             : /// when we can prove a relationship between the operands.
     998        8712 : static bool isICmpTrue(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
     999             :                        const SimplifyQuery &Q, unsigned MaxRecurse) {
    1000        8712 :   Value *V = SimplifyICmpInst(Pred, LHS, RHS, Q, MaxRecurse);
    1001          84 :   Constant *C = dyn_cast_or_null<Constant>(V);
    1002          84 :   return (C && C->isAllOnesValue());
    1003             : }
    1004             : 
    1005        8714 : static Value *simplifyUnsignedDivRem(Value *Op0, Value *Op1,
    1006             :                                      const SimplifyQuery &Q,
    1007             :                                      unsigned MaxRecurse, bool IsDiv) {
    1008             :   // Recursion is always used, so bail out at once if we already hit the limit.
    1009        8714 :   if (!MaxRecurse--)
    1010             :     return nullptr;
    1011             : 
    1012             :   // If we can prove that the quotient is unsigned less than the divisor, then
    1013             :   // we know the answer:
    1014             :   // X / Y --> 0
    1015             :   // X % Y --> X
    1016        8712 :   if (isICmpTrue(ICmpInst::ICMP_ULT, Op0, Op1, Q, MaxRecurse))
    1017           9 :     return IsDiv ? Constant::getNullValue(Op0->getType()) : Op0;
    1018             : 
    1019             :   return nullptr;
    1020             : }
    1021             : 
    1022             : /// Given operands for an SDiv, see if we can fold the result.
    1023             : /// If not, this returns null.
    1024         160 : static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
    1025             :                                unsigned MaxRecurse) {
    1026        6453 :   if (Value *V = simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse))
    1027             :     return V;
    1028             : 
    1029         145 :   return nullptr;
    1030             : }
    1031             : 
    1032        6293 : Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
    1033        6293 :   return ::SimplifySDivInst(Op0, Op1, Q, RecursionLimit);
    1034             : }
    1035             : 
    1036             : /// Given operands for a UDiv, see if we can fold the result.
    1037             : /// If not, this returns null.
    1038        3584 : static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
    1039             :                                unsigned MaxRecurse) {
    1040        3584 :   if (Value *V = simplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse))
    1041             :     return V;
    1042             : 
    1043        3507 :   if (Value *V = simplifyUnsignedDivRem(Op0, Op1, Q, MaxRecurse, true))
    1044             :     return V;
    1045             : 
    1046        3503 :   return nullptr;
    1047             : }
    1048             : 
    1049        3369 : Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
    1050        3369 :   return ::SimplifyUDivInst(Op0, Op1, Q, RecursionLimit);
    1051             : }
    1052             : 
    1053             : /// Given operands for an SRem, see if we can fold the result.
    1054             : /// If not, this returns null.
    1055         283 : static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
    1056             :                                unsigned MaxRecurse) {
    1057        1042 :   if (Value *V = simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse))
    1058             :     return V;
    1059             : 
    1060         178 :   return nullptr;
    1061             : }
    1062             : 
    1063         759 : Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
    1064         759 :   return ::SimplifySRemInst(Op0, Op1, Q, RecursionLimit);
    1065             : }
    1066             : 
    1067             : /// Given operands for a URem, see if we can fold the result.
    1068             : /// If not, this returns null.
    1069        5797 : static Value *SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
    1070             :                                unsigned MaxRecurse) {
    1071        5797 :   if (Value *V = simplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse))
    1072             :     return V;
    1073             : 
    1074        5207 :   if (Value *V = simplifyUnsignedDivRem(Op0, Op1, Q, MaxRecurse, false))
    1075             :     return V;
    1076             : 
    1077        5202 :   return nullptr;
    1078             : }
    1079             : 
    1080        4465 : Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
    1081        4465 :   return ::SimplifyURemInst(Op0, Op1, Q, RecursionLimit);
    1082             : }
    1083             : 
    1084             : /// Returns true if a shift by \c Amount always yields undef.
    1085       83550 : static bool isUndefShift(Value *Amount) {
    1086       71570 :   Constant *C = dyn_cast<Constant>(Amount);
    1087             :   if (!C)
    1088             :     return false;
    1089             : 
    1090             :   // X shift by undef -> undef because it may shift by the bitwidth.
    1091      143140 :   if (isa<UndefValue>(C))
    1092             :     return true;
    1093             : 
    1094             :   // Shifting by the bitwidth or more is undefined.
    1095      140988 :   if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
    1096      208392 :     if (CI->getValue().getLimitedValue() >=
    1097       69464 :         CI->getType()->getScalarSizeInBits())
    1098             :       return true;
    1099             : 
    1100             :   // If all lanes of a vector shift are undefined the whole shift is.
    1101      214341 :   if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
    1102        4173 :     for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I)
    1103        2113 :       if (!isUndefShift(C->getAggregateElement(I)))
    1104             :         return false;
    1105             :     return true;
    1106             :   }
    1107             : 
    1108             :   return false;
    1109             : }
    1110             : 
    1111             : /// Given operands for an Shl, LShr or AShr, see if we can fold the result.
    1112             : /// If not, this returns null.
    1113       88441 : static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0,
    1114             :                             Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) {
    1115       88441 :   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
    1116             :     return C;
    1117             : 
    1118             :   // 0 shift by X -> 0
    1119       91374 :   if (match(Op0, m_Zero()))
    1120          20 :     return Op0;
    1121             : 
    1122             :   // X shift by 0 -> X
    1123      151070 :   if (match(Op1, m_Zero()))
    1124          88 :     return Op0;
    1125             : 
    1126             :   // Fold undefined shifts.
    1127       81437 :   if (isUndefShift(Op1))
    1128          19 :     return UndefValue::get(Op0->getType());
    1129             : 
    1130             :   // If the operation is with the result of a select instruction, check whether
    1131             :   // operating on either branch of the select always yields the same value.
    1132      162070 :   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
    1133         789 :     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
    1134             :       return V;
    1135             : 
    1136             :   // If the operation is with the result of a phi instruction, check whether
    1137             :   // operating on all incoming values of the phi always yields the same value.
    1138      157270 :   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
    1139        5726 :     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
    1140             :       return V;
    1141             : 
    1142             :   // If any bits in the shift amount make that value greater than or equal to
    1143             :   // the number of bits in the type, the shift is undefined.
    1144      162834 :   KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    1145      162834 :   if (Known.One.getLimitedValue() >= Known.getBitWidth())
    1146           4 :     return UndefValue::get(Op0->getType());
    1147             : 
    1148             :   // If all valid bits in the shift amount are known zero, the first operand is
    1149             :   // unchanged.
    1150      162826 :   unsigned NumValidShiftBits = Log2_32_Ceil(Known.getBitWidth());
    1151       81413 :   if (Known.countMinTrailingZeros() >= NumValidShiftBits)
    1152           6 :     return Op0;
    1153             : 
    1154             :   return nullptr;
    1155             : }
    1156             : 
    1157             : /// \brief Given operands for an Shl, LShr or AShr, see if we can
    1158             : /// fold the result.  If not, this returns null.
    1159       44664 : static Value *SimplifyRightShift(Instruction::BinaryOps Opcode, Value *Op0,
    1160             :                                  Value *Op1, bool isExact, const SimplifyQuery &Q,
    1161             :                                  unsigned MaxRecurse) {
    1162       44664 :   if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse))
    1163             :     return V;
    1164             : 
    1165             :   // X >> X -> 0
    1166       42758 :   if (Op0 == Op1)
    1167           3 :     return Constant::getNullValue(Op0->getType());
    1168             : 
    1169             :   // undef >> X -> 0
    1170             :   // undef >> X -> undef (if it's exact)
    1171       85510 :   if (match(Op0, m_Undef()))
    1172           3 :     return isExact ? Op0 : Constant::getNullValue(Op0->getType());
    1173             : 
    1174             :   // The low bit cannot be shifted out of an exact shift if it is set.
    1175       42752 :   if (isExact) {
    1176       32782 :     KnownBits Op0Known = computeKnownBits(Op0, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
    1177       16393 :     if (Op0Known.One[0])
    1178           4 :       return Op0;
    1179             :   }
    1180             : 
    1181             :   return nullptr;
    1182             : }
    1183             : 
    1184             : /// Given operands for an Shl, see if we can fold the result.
    1185             : /// If not, this returns null.
    1186       43777 : static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
    1187             :                               const SimplifyQuery &Q, unsigned MaxRecurse) {
    1188       43777 :   if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
    1189             :     return V;
    1190             : 
    1191             :   // undef << X -> 0
    1192             :   // undef << X -> undef if (if it's NSW/NUW)
    1193       77298 :   if (match(Op0, m_Undef()))
    1194           4 :     return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
    1195             : 
    1196             :   // (X >> A) << A -> X
    1197             :   Value *X;
    1198      193225 :   if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
    1199          13 :     return X;
    1200             :   return nullptr;
    1201             : }
    1202             : 
    1203       34247 : Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
    1204             :                              const SimplifyQuery &Q) {
    1205       34247 :   return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
    1206             : }
    1207             : 
    1208             : /// Given operands for an LShr, see if we can fold the result.
    1209             : /// If not, this returns null.
    1210       26814 : static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
    1211             :                                const SimplifyQuery &Q, unsigned MaxRecurse) {
    1212       53628 :   if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q,
    1213       26814 :                                     MaxRecurse))
    1214             :       return V;
    1215             : 
    1216             :   // (X << A) >> A -> X
    1217             :   Value *X;
    1218      100180 :   if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1))))
    1219           7 :     return X;
    1220             : 
    1221             :   return nullptr;
    1222             : }
    1223             : 
    1224       23914 : Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
    1225             :                               const SimplifyQuery &Q) {
    1226       23914 :   return ::SimplifyLShrInst(Op0, Op1, isExact, Q, RecursionLimit);
    1227             : }
    1228             : 
    1229             : /// Given operands for an AShr, see if we can fold the result.
    1230             : /// If not, this returns null.
    1231       17850 : static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
    1232             :                                const SimplifyQuery &Q, unsigned MaxRecurse) {
    1233       35700 :   if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q,
    1234       17850 :                                     MaxRecurse))
    1235             :     return V;
    1236             : 
    1237             :   // all ones >>a X -> all ones
    1238       17772 :   if (match(Op0, m_AllOnes()))
    1239             :     return Op0;
    1240             : 
    1241             :   // (X << A) >> A -> X
    1242             :   Value *X;
    1243       70784 :   if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1))))
    1244           3 :     return X;
    1245             : 
    1246             :   // Arithmetic shifting an all-sign-bit value is a no-op.
    1247       17693 :   unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    1248       17693 :   if (NumSignBits == Op0->getType()->getScalarSizeInBits())
    1249             :     return Op0;
    1250             : 
    1251       17686 :   return nullptr;
    1252             : }
    1253             : 
    1254       17674 : Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
    1255             :                               const SimplifyQuery &Q) {
    1256       17674 :   return ::SimplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit);
    1257             : }
    1258             : 
    1259             : /// Commuted variants are assumed to be handled by calling this function again
    1260             : /// with the parameters swapped.
    1261       14103 : static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
    1262             :                                          ICmpInst *UnsignedICmp, bool IsAnd) {
    1263             :   Value *X, *Y;
    1264             : 
    1265             :   ICmpInst::Predicate EqPred;
    1266       60483 :   if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
    1267        8142 :       !ICmpInst::isEquality(EqPred))
    1268             :     return nullptr;
    1269             : 
    1270             :   ICmpInst::Predicate UnsignedPred;
    1271       16022 :   if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
    1272          13 :       ICmpInst::isUnsigned(UnsignedPred))
    1273             :     ;
    1274           0 :   else if (match(UnsignedICmp,
    1275       15968 :                  m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) &&
    1276           0 :            ICmpInst::isUnsigned(UnsignedPred))
    1277           0 :     UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
    1278             :   else
    1279             :     return nullptr;
    1280             : 
    1281             :   // X < Y && Y != 0  -->  X < Y
    1282             :   // X < Y || Y != 0  -->  Y != 0
    1283           7 :   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
    1284           2 :     return IsAnd ? UnsignedICmp : ZeroICmp;
    1285             : 
    1286             :   // X >= Y || Y != 0  -->  true
    1287             :   // X >= Y || Y == 0  -->  X >= Y
    1288           5 :   if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) {
    1289           3 :     if (EqPred == ICmpInst::ICMP_NE)
    1290           4 :       return getTrue(UnsignedICmp->getType());
    1291             :     return UnsignedICmp;
    1292             :   }
    1293             : 
    1294             :   // X < Y && Y == 0  -->  false
    1295           2 :   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
    1296             :       IsAnd)
    1297           2 :     return getFalse(UnsignedICmp->getType());
    1298             : 
    1299             :   return nullptr;
    1300             : }
    1301             : 
    1302             : /// Commuted variants are assumed to be handled by calling this function again
    1303             : /// with the parameters swapped.
    1304        4200 : static Value *simplifyAndOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) {
    1305             :   ICmpInst::Predicate Pred0, Pred1;
    1306             :   Value *A ,*B;
    1307       16800 :   if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
    1308       16984 :       !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
    1309             :     return nullptr;
    1310             : 
    1311             :   // We have (icmp Pred0, A, B) & (icmp Pred1, A, B).
    1312             :   // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
    1313             :   // can eliminate Op1 from this 'and'.
    1314         184 :   if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
    1315             :     return Op0;
    1316             : 
    1317             :   // Check for any combination of predicates that are guaranteed to be disjoint.
    1318         273 :   if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
    1319           9 :       (Pred0 == ICmpInst::ICMP_EQ && ICmpInst::isFalseWhenEqual(Pred1)) ||
    1320         162 :       (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT) ||
    1321          13 :       (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT))
    1322          78 :     return getFalse(Op0->getType());
    1323             : 
    1324             :   return nullptr;
    1325             : }
    1326             : 
    1327             : /// Commuted variants are assumed to be handled by calling this function again
    1328             : /// with the parameters swapped.
    1329        9717 : static Value *simplifyOrOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) {
    1330             :   ICmpInst::Predicate Pred0, Pred1;
    1331             :   Value *A ,*B;
    1332       38868 :   if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
    1333       39157 :       !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
    1334             :     return nullptr;
    1335             : 
    1336             :   // We have (icmp Pred0, A, B) | (icmp Pred1, A, B).
    1337             :   // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
    1338             :   // can eliminate Op0 from this 'or'.
    1339         289 :   if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
    1340             :     return Op1;
    1341             : 
    1342             :   // Check for any combination of predicates that cover the entire range of
    1343             :   // possibilities.
    1344         353 :   if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
    1345          12 :       (Pred0 == ICmpInst::ICMP_NE && ICmpInst::isTrueWhenEqual(Pred1)) ||
    1346         202 :       (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGE) ||
    1347          13 :       (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGE))
    1348          74 :     return getTrue(Op0->getType());
    1349             : 
    1350             :   return nullptr;
    1351             : }
    1352             : 
    1353             : /// Test if a pair of compares with a shared operand and 2 constants has an
    1354             : /// empty set intersection, full set union, or if one compare is a superset of
    1355             : /// the other.
    1356        6834 : static Value *simplifyAndOrOfICmpsWithConstants(ICmpInst *Cmp0, ICmpInst *Cmp1,
    1357             :                                                 bool IsAnd) {
    1358             :   // Look for this pattern: {and/or} (icmp X, C0), (icmp X, C1)).
    1359       20502 :   if (Cmp0->getOperand(0) != Cmp1->getOperand(0))
    1360             :     return nullptr;
    1361             : 
    1362             :   const APInt *C0, *C1;
    1363        7036 :   if (!match(Cmp0->getOperand(1), m_APInt(C0)) ||
    1364        3189 :       !match(Cmp1->getOperand(1), m_APInt(C1)))
    1365             :     return nullptr;
    1366             : 
    1367        1539 :   auto Range0 = ConstantRange::makeExactICmpRegion(Cmp0->getPredicate(), *C0);
    1368        1539 :   auto Range1 = ConstantRange::makeExactICmpRegion(Cmp1->getPredicate(), *C1);
    1369             : 
    1370             :   // For and-of-compares, check if the intersection is empty:
    1371             :   // (icmp X, C0) && (icmp X, C1) --> empty set --> false
    1372         513 :   if (IsAnd && Range0.intersectWith(Range1).isEmptySet())
    1373          96 :     return getFalse(Cmp0->getType());
    1374             : 
    1375             :   // For or-of-compares, check if the union is full:
    1376             :   // (icmp X, C0) || (icmp X, C1) --> full set --> true
    1377         465 :   if (!IsAnd && Range0.unionWith(Range1).isFullSet())
    1378          86 :     return getTrue(Cmp0->getType());
    1379             : 
    1380             :   // Is one range a superset of the other?
    1381             :   // If this is and-of-compares, take the smaller set:
    1382             :   // (icmp sgt X, 4) && (icmp sgt X, 42) --> icmp sgt X, 42
    1383             :   // If this is or-of-compares, take the larger set:
    1384             :   // (icmp sgt X, 4) || (icmp sgt X, 42) --> icmp sgt X, 4
    1385         422 :   if (Range0.contains(Range1))
    1386          99 :     return IsAnd ? Cmp1 : Cmp0;
    1387         323 :   if (Range1.contains(Range0))
    1388          90 :     return IsAnd ? Cmp0 : Cmp1;
    1389             : 
    1390             :   return nullptr;
    1391             : }
    1392             : 
    1393        3800 : static Value *simplifyAndOfICmpsWithAdd(ICmpInst *Op0, ICmpInst *Op1) {
    1394             :   // (icmp (add V, C0), C1) & (icmp V, C0)
    1395             :   ICmpInst::Predicate Pred0, Pred1;
    1396             :   const APInt *C0, *C1;
    1397             :   Value *V;
    1398       22800 :   if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
    1399             :     return nullptr;
    1400             : 
    1401         222 :   if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
    1402             :     return nullptr;
    1403             : 
    1404          36 :   auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
    1405          24 :   if (AddInst->getOperand(1) != Op1->getOperand(1))
    1406             :     return nullptr;
    1407             : 
    1408          12 :   Type *ITy = Op0->getType();
    1409          12 :   bool isNSW = AddInst->hasNoSignedWrap();
    1410          12 :   bool isNUW = AddInst->hasNoUnsignedWrap();
    1411             : 
    1412          48 :   const APInt Delta = *C1 - *C0;
    1413          12 :   if (C0->isStrictlyPositive()) {
    1414          12 :     if (Delta == 2) {
    1415           6 :       if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT)
    1416           2 :         return getFalse(ITy);
    1417           4 :       if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW)
    1418           2 :         return getFalse(ITy);
    1419             :     }
    1420           8 :     if (Delta == 1) {
    1421           6 :       if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT)
    1422           2 :         return getFalse(ITy);
    1423           4 :       if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW)
    1424           2 :         return getFalse(ITy);
    1425             :     }
    1426             :   }
    1427           8 :   if (C0->getBoolValue() && isNUW) {
    1428           4 :     if (Delta == 2)
    1429           2 :       if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT)
    1430           2 :         return getFalse(ITy);
    1431           2 :     if (Delta == 1)
    1432           2 :       if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT)
    1433           2 :         return getFalse(ITy);
    1434             :   }
    1435             : 
    1436             :   return nullptr;
    1437             : }
    1438             : 
    1439        2130 : static Value *simplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
    1440        2130 :   if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true))
    1441             :     return X;
    1442        2130 :   if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/true))
    1443             :     return X;
    1444             : 
    1445        2128 :   if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1))
    1446             :     return X;
    1447        2072 :   if (Value *X = simplifyAndOfICmpsWithSameOperands(Op1, Op0))
    1448             :     return X;
    1449             : 
    1450        2053 :   if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, true))
    1451             :     return X;
    1452             : 
    1453        1906 :   if (Value *X = simplifyAndOfICmpsWithAdd(Op0, Op1))
    1454             :     return X;
    1455        1894 :   if (Value *X = simplifyAndOfICmpsWithAdd(Op1, Op0))
    1456             :     return X;
    1457             : 
    1458        1894 :   return nullptr;
    1459             : }
    1460             : 
    1461        9284 : static Value *simplifyOrOfICmpsWithAdd(ICmpInst *Op0, ICmpInst *Op1) {
    1462             :   // (icmp (add V, C0), C1) | (icmp V, C0)
    1463             :   ICmpInst::Predicate Pred0, Pred1;
    1464             :   const APInt *C0, *C1;
    1465             :   Value *V;
    1466       55704 :   if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
    1467             :     return nullptr;
    1468             : 
    1469         127 :   if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
    1470             :     return nullptr;
    1471             : 
    1472          39 :   auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
    1473          26 :   if (AddInst->getOperand(1) != Op1->getOperand(1))
    1474             :     return nullptr;
    1475             : 
    1476          12 :   Type *ITy = Op0->getType();
    1477          12 :   bool isNSW = AddInst->hasNoSignedWrap();
    1478          12 :   bool isNUW = AddInst->hasNoUnsignedWrap();
    1479             : 
    1480          48 :   const APInt Delta = *C1 - *C0;
    1481          12 :   if (C0->isStrictlyPositive()) {
    1482          12 :     if (Delta == 2) {
    1483           6 :       if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE)
    1484           2 :         return getTrue(ITy);
    1485           4 :       if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW)
    1486           2 :         return getTrue(ITy);
    1487             :     }
    1488           8 :     if (Delta == 1) {
    1489           6 :       if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE)
    1490           2 :         return getTrue(ITy);
    1491           4 :       if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW)
    1492           2 :         return getTrue(ITy);
    1493             :     }
    1494             :   }
    1495           8 :   if (C0->getBoolValue() && isNUW) {
    1496           4 :     if (Delta == 2)
    1497           2 :       if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE)
    1498           2 :         return getTrue(ITy);
    1499           2 :     if (Delta == 1)
    1500           2 :       if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE)
    1501           2 :         return getTrue(ITy);
    1502             :   }
    1503             : 
    1504             :   return nullptr;
    1505             : }
    1506             : 
    1507        4922 : static Value *simplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
    1508        4922 :   if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false))
    1509             :     return X;
    1510        4921 :   if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/false))
    1511             :     return X;
    1512             : 
    1513        4918 :   if (Value *X = simplifyOrOfICmpsWithSameOperands(Op0, Op1))
    1514             :     return X;
    1515        4799 :   if (Value *X = simplifyOrOfICmpsWithSameOperands(Op1, Op0))
    1516             :     return X;
    1517             : 
    1518        4781 :   if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, false))
    1519             :     return X;
    1520             : 
    1521        4648 :   if (Value *X = simplifyOrOfICmpsWithAdd(Op0, Op1))
    1522             :     return X;
    1523        4636 :   if (Value *X = simplifyOrOfICmpsWithAdd(Op1, Op0))
    1524             :     return X;
    1525             : 
    1526        4636 :   return nullptr;
    1527             : }
    1528             : 
    1529      155623 : static Value *simplifyAndOrOfICmps(Value *Op0, Value *Op1, bool IsAnd) {
    1530             :   // Look through casts of the 'and' operands to find compares.
    1531      155623 :   auto *Cast0 = dyn_cast<CastInst>(Op0);
    1532      155623 :   auto *Cast1 = dyn_cast<CastInst>(Op1);
    1533      158358 :   if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
    1534        1750 :       Cast0->getSrcTy() == Cast1->getSrcTy()) {
    1535             :     Op0 = Cast0->getOperand(0);
    1536             :     Op1 = Cast1->getOperand(0);
    1537             :   }
    1538             : 
    1539      155623 :   auto *Cmp0 = dyn_cast<ICmpInst>(Op0);
    1540      155623 :   auto *Cmp1 = dyn_cast<ICmpInst>(Op1);
    1541      155623 :   if (!Cmp0 || !Cmp1)
    1542             :     return nullptr;
    1543             : 
    1544             :   Value *V =
    1545        7052 :       IsAnd ? simplifyAndOfICmps(Cmp0, Cmp1) : simplifyOrOfICmps(Cmp0, Cmp1);
    1546        7052 :   if (!V)
    1547             :     return nullptr;
    1548         522 :   if (!Cast0)
    1549             :     return V;
    1550             : 
    1551             :   // If we looked through casts, we can only handle a constant simplification
    1552             :   // because we are not allowed to create a cast instruction here.
    1553           8 :   if (auto *C = dyn_cast<Constant>(V))
    1554          16 :     return ConstantExpr::getCast(Cast0->getOpcode(), C, Cast0->getType());
    1555             : 
    1556             :   return nullptr;
    1557             : }
    1558             : 
    1559             : /// Given operands for an And, see if we can fold the result.
    1560             : /// If not, this returns null.
    1561       88800 : static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
    1562             :                               unsigned MaxRecurse) {
    1563       88800 :   if (Constant *C = foldOrCommuteConstant(Instruction::And, Op0, Op1, Q))
    1564             :     return C;
    1565             : 
    1566             :   // X & undef -> 0
    1567      162466 :   if (match(Op1, m_Undef()))
    1568           1 :     return Constant::getNullValue(Op0->getType());
    1569             : 
    1570             :   // X & X = X
    1571       81232 :   if (Op0 == Op1)
    1572             :     return Op0;
    1573             : 
    1574             :   // X & 0 = 0
    1575      130775 :   if (match(Op1, m_Zero()))
    1576         908 :     return Op1;
    1577             : 
    1578             :   // X & -1 = X
    1579      128959 :   if (match(Op1, m_AllOnes()))
    1580        4108 :     return Op0;
    1581             : 
    1582             :   // A & ~A  =  ~A & A  =  0
    1583      456932 :   if (match(Op0, m_Not(m_Specific(Op1))) ||
    1584      380707 :       match(Op1, m_Not(m_Specific(Op0))))
    1585          35 :     return Constant::getNullValue(Op0->getType());
    1586             : 
    1587             :   // (A | ?) & A = A
    1588      304496 :   if (match(Op0, m_c_Or(m_Specific(Op1), m_Value())))
    1589             :     return Op1;
    1590             : 
    1591             :   // A & (A | ?) = A
    1592      304396 :   if (match(Op1, m_c_Or(m_Specific(Op0), m_Value())))
    1593             :     return Op0;
    1594             : 
    1595             :   // A mask that only clears known zeros of a shifted value is a no-op.
    1596             :   Value *X;
    1597             :   const APInt *Mask;
    1598             :   const APInt *ShAmt;
    1599      152168 :   if (match(Op1, m_APInt(Mask))) {
    1600             :     // If all bits in the inverted and shifted mask are clear:
    1601             :     // and (shl X, ShAmt), Mask --> shl X, ShAmt
    1602      269294 :     if (match(Op0, m_Shl(m_Value(X), m_APInt(ShAmt))) &&
    1603      182492 :         (~(*Mask)).lshr(*ShAmt).isNullValue())
    1604          29 :       return Op0;
    1605             : 
    1606             :     // If all bits in the inverted and shifted mask are clear:
    1607             :     // and (lshr X, ShAmt), Mask --> lshr X, ShAmt
    1608      275464 :     if (match(Op0, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
    1609      195064 :         (~(*Mask)).shl(*ShAmt).isNullValue())
    1610          34 :       return Op0;
    1611             :   }
    1612             : 
    1613             :   // A & (-A) = A if A is a power of two or zero.
    1614      456125 :   if (match(Op0, m_Neg(m_Specific(Op1))) ||
    1615      380101 :       match(Op1, m_Neg(m_Specific(Op0)))) {
    1616          11 :     if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
    1617          11 :                                Q.DT))
    1618           2 :       return Op0;
    1619           9 :     if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
    1620           9 :                                Q.DT))
    1621           0 :       return Op1;
    1622             :   }
    1623             : 
    1624       76019 :   if (Value *V = simplifyAndOrOfICmps(Op0, Op1, true))
    1625             :     return V;
    1626             : 
    1627             :   // Try some generic simplifications for associative operations.
    1628      151566 :   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
    1629       75783 :                                           MaxRecurse))
    1630             :     return V;
    1631             : 
    1632             :   // And distributes over Or.  Try some generic simplifications based on this.
    1633      149812 :   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
    1634       74906 :                              Q, MaxRecurse))
    1635             :     return V;
    1636             : 
    1637             :   // And distributes over Xor.  Try some generic simplifications based on this.
    1638      148504 :   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
    1639       74252 :                              Q, MaxRecurse))
    1640             :     return V;
    1641             : 
    1642             :   // If the operation is with the result of a select instruction, check whether
    1643             :   // operating on either branch of the select always yields the same value.
    1644      148323 :   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
    1645         350 :     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
    1646         175 :                                          MaxRecurse))
    1647             :       return V;
    1648             : 
    1649             :   // If the operation is with the result of a phi instruction, check whether
    1650             :   // operating on all incoming values of the phi always yields the same value.
    1651      139526 :   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
    1652       19446 :     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
    1653        9723 :                                       MaxRecurse))
    1654             :       return V;
    1655             : 
    1656             :   return nullptr;
    1657             : }
    1658             : 
    1659       57426 : Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
    1660       57426 :   return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
    1661             : }
    1662             : 
    1663             : /// Given operands for an Or, see if we can fold the result.
    1664             : /// If not, this returns null.
    1665       89031 : static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
    1666             :                              unsigned MaxRecurse) {
    1667       89031 :   if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q))
    1668             :     return C;
    1669             : 
    1670             :   // X | undef -> -1
    1671      164460 :   if (match(Op1, m_Undef()))
    1672          14 :     return Constant::getAllOnesValue(Op0->getType());
    1673             : 
    1674             :   // X | X = X
    1675       82216 :   if (Op0 == Op1)
    1676             :     return Op0;
    1677             : 
    1678             :   // X | 0 = X
    1679      112307 :   if (match(Op1, m_Zero()))
    1680         496 :     return Op0;
    1681             : 
    1682             :   // X | -1 = -1
    1683      111315 :   if (match(Op1, m_AllOnes()))
    1684          22 :     return Op1;
    1685             : 
    1686             :   // A | ~A  =  ~A | A  =  -1
    1687      489814 :   if (match(Op0, m_Not(m_Specific(Op1))) ||
    1688      408001 :       match(Op1, m_Not(m_Specific(Op0))))
    1689        1920 :     return Constant::getAllOnesValue(Op0->getType());
    1690             : 
    1691             :   // (A & ?) | A = A
    1692      318900 :   if (match(Op0, m_c_And(m_Specific(Op1), m_Value())))
    1693             :     return Op1;
    1694             : 
    1695             :   // A | (A & ?) = A
    1696      318764 :   if (match(Op1, m_c_And(m_Specific(Op0), m_Value())))
    1697             :     return Op0;
    1698             : 
    1699             :   // ~(A & ?) | A = -1
    1700      398110 :   if (match(Op0, m_Not(m_c_And(m_Specific(Op1), m_Value()))))
    1701           2 :     return Constant::getAllOnesValue(Op1->getType());
    1702             : 
    1703             :   // A | ~(A & ?) = -1
    1704      398100 :   if (match(Op1, m_Not(m_c_And(m_Specific(Op1), m_Value()))))
    1705           0 :     return Constant::getAllOnesValue(Op0->getType());
    1706             : 
    1707             :   Value *A, *B;
    1708             :   // (A & ~B) | (A ^ B) -> (A ^ B)
    1709             :   // (~B & A) | (A ^ B) -> (A ^ B)
    1710             :   // (A & ~B) | (B ^ A) -> (B ^ A)
    1711             :   // (~B & A) | (B ^ A) -> (B ^ A)
    1712      401257 :   if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
    1713      101717 :       (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
    1714       98550 :        match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
    1715           4 :     return Op1;
    1716             : 
    1717             :   // Commute the 'or' operands.
    1718             :   // (A ^ B) | (A & ~B) -> (A ^ B)
    1719             :   // (A ^ B) | (~B & A) -> (A ^ B)
    1720             :   // (B ^ A) | (A & ~B) -> (B ^ A)
    1721             :   // (B ^ A) | (~B & A) -> (B ^ A)
    1722      398602 :   if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
    1723       83268 :       (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
    1724       82736 :        match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
    1725           4 :     return Op0;
    1726             : 
    1727             :   // (A & B) | (~A ^ B) -> (~A ^ B)
    1728             :   // (B & A) | (~A ^ B) -> (~A ^ B)
    1729             :   // (A & B) | (B ^ ~A) -> (B ^ ~A)
    1730             :   // (B & A) | (B ^ ~A) -> (B ^ ~A)
    1731      414692 :   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
    1732      196034 :       (match(Op1, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
    1733      179392 :        match(Op1, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
    1734           4 :     return Op1;
    1735             : 
    1736             :   // (~A ^ B) | (A & B) -> (~A ^ B)
    1737             :   // (~A ^ B) | (B & A) -> (~A ^ B)
    1738             :   // (B ^ ~A) | (A & B) -> (B ^ ~A)
    1739             :   // (B ^ ~A) | (B & A) -> (B ^ ~A)
    1740      405478 :   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
    1741      131672 :       (match(Op0, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
    1742      124224 :        match(Op0, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
    1743           4 :     return Op0;
    1744             : 
    1745       79604 :   if (Value *V = simplifyAndOrOfICmps(Op0, Op1, false))
    1746             :     return V;
    1747             : 
    1748             :   // Try some generic simplifications for associative operations.
    1749      158636 :   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
    1750       79318 :                                           MaxRecurse))
    1751             :     return V;
    1752             : 
    1753             :   // Or distributes over And.  Try some generic simplifications based on this.
    1754      158384 :   if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
    1755       79192 :                              MaxRecurse))
    1756             :     return V;
    1757             : 
    1758             :   // If the operation is with the result of a select instruction, check whether
    1759             :   // operating on either branch of the select always yields the same value.
    1760      158004 :   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
    1761         900 :     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
    1762         450 :                                          MaxRecurse))
    1763             :       return V;
    1764             : 
    1765             :   // (A & C1)|(B & C2)
    1766             :   const APInt *C1, *C2;
    1767      407596 :   if (match(Op0, m_And(m_Value(A), m_APInt(C1))) &&
    1768      125736 :       match(Op1, m_And(m_Value(B), m_APInt(C2)))) {
    1769        6024 :     if (*C1 == ~*C2) {
    1770             :       // (A & C1)|(B & C2)
    1771             :       // If we have: ((V + N) & C1) | (V & C2)
    1772             :       // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
    1773             :       // replace with V+N.
    1774             :       Value *N;
    1775         242 :       if (C2->isMask() && // C2 == 0+1+
    1776         466 :           match(A, m_c_Add(m_Specific(B), m_Value(N)))) {
    1777             :         // Add commutes, try both ways.
    1778           4 :         if (MaskedValueIsZero(N, *C2, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
    1779          11 :           return A;
    1780             :       }
    1781             :       // Or commutes, try both ways.
    1782         223 :       if (C1->isMask() &&
    1783         403 :           match(B, m_c_Add(m_Specific(A), m_Value(N)))) {
    1784             :         // Add commutes, try both ways.
    1785           3 :         if (MaskedValueIsZero(N, *C1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
    1786           3 :           return B;
    1787             :       }
    1788             :     }
    1789             :   }
    1790             : 
    1791             :   // If the operation is with the result of a phi instruction, check whether
    1792             :   // operating on all incoming values of the phi always yields the same value.
    1793      155405 :   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
    1794        5338 :     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
    1795             :       return V;
    1796             : 
    1797             :   return nullptr;
    1798             : }
    1799             : 
    1800       33740 : Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
    1801       33740 :   return ::SimplifyOrInst(Op0, Op1, Q, RecursionLimit);
    1802             : }
    1803             : 
    1804             : /// Given operands for a Xor, see if we can fold the result.
    1805             : /// If not, this returns null.
    1806       52021 : static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
    1807             :                               unsigned MaxRecurse) {
    1808       52021 :   if (Constant *C = foldOrCommuteConstant(Instruction::Xor, Op0, Op1, Q))
    1809             :     return C;
    1810             : 
    1811             :   // A ^ undef -> undef
    1812       98260 :   if (match(Op1, m_Undef()))
    1813             :     return Op1;
    1814             : 
    1815             :   // A ^ 0 = A
    1816       80423 :   if (match(Op1, m_Zero()))
    1817        2022 :     return Op0;
    1818             : 
    1819             :   // A ^ A = 0
    1820       47108 :   if (Op0 == Op1)
    1821          18 :     return Constant::getNullValue(Op0->getType());
    1822             : 
    1823             :   // A ^ ~A  =  ~A ^ A  =  -1
    1824      282540 :   if (match(Op0, m_Not(m_Specific(Op1))) ||
    1825      235450 :       match(Op1, m_Not(m_Specific(Op0))))
    1826           2 :     return Constant::getAllOnesValue(Op0->getType());
    1827             : 
    1828             :   // Try some generic simplifications for associative operations.
    1829       94176 :   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
    1830       47088 :                                           MaxRecurse))
    1831             :     return V;
    1832             : 
    1833             :   // Threading Xor over selects and phi nodes is pointless, so don't bother.
    1834             :   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
    1835             :   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
    1836             :   // only if B and C are equal.  If B and C are equal then (since we assume
    1837             :   // that operands have already been simplified) "select(cond, B, C)" should
    1838             :   // have been simplified to the common value of B and C already.  Analysing
    1839             :   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
    1840             :   // for threading over phi nodes.
    1841             : 
    1842       45132 :   return nullptr;
    1843             : }
    1844             : 
    1845       35507 : Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
    1846       35507 :   return ::SimplifyXorInst(Op0, Op1, Q, RecursionLimit);
    1847             : }
    1848             : 
    1849             : 
    1850             : static Type *GetCompareTy(Value *Op) {
    1851     2770818 :   return CmpInst::makeCmpResultType(Op->getType());
    1852             : }
    1853             : 
    1854             : /// Rummage around inside V looking for something equivalent to the comparison
    1855             : /// "LHS Pred RHS". Return such a value if found, otherwise return null.
    1856             : /// Helper function for analyzing max/min idioms.
    1857         353 : static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
    1858             :                                          Value *LHS, Value *RHS) {
    1859         182 :   SelectInst *SI = dyn_cast<SelectInst>(V);
    1860             :   if (!SI)
    1861             :     return nullptr;
    1862         364 :   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
    1863             :   if (!Cmp)
    1864             :     return nullptr;
    1865         364 :   Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
    1866         182 :   if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
    1867             :     return Cmp;
    1868         170 :   if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
    1869         170 :       LHS == CmpRHS && RHS == CmpLHS)
    1870             :     return Cmp;
    1871             :   return nullptr;
    1872             : }
    1873             : 
    1874             : // A significant optimization not implemented here is assuming that alloca
    1875             : // addresses are not equal to incoming argument values. They don't *alias*,
    1876             : // as we say, but that doesn't mean they aren't equal, so we take a
    1877             : // conservative approach.
    1878             : //
    1879             : // This is inspired in part by C++11 5.10p1:
    1880             : //   "Two pointers of the same type compare equal if and only if they are both
    1881             : //    null, both point to the same function, or both represent the same
    1882             : //    address."
    1883             : //
    1884             : // This is pretty permissive.
    1885             : //
    1886             : // It's also partly due to C11 6.5.9p6:
    1887             : //   "Two pointers compare equal if and only if both are null pointers, both are
    1888             : //    pointers to the same object (including a pointer to an object and a
    1889             : //    subobject at its beginning) or function, both are pointers to one past the
    1890             : //    last element of the same array object, or one is a pointer to one past the
    1891             : //    end of one array object and the other is a pointer to the start of a
    1892             : //    different array object that happens to immediately follow the first array
    1893             : //    object in the address space.)
    1894             : //
    1895             : // C11's version is more restrictive, however there's no reason why an argument
    1896             : // couldn't be a one-past-the-end value for a stack object in the caller and be
    1897             : // equal to the beginning of a stack object in the callee.
    1898             : //
    1899             : // If the C and C++ standards are ever made sufficiently restrictive in this
    1900             : // area, it may be possible to update LLVM's semantics accordingly and reinstate
    1901             : // this optimization.
    1902             : static Constant *
    1903      207723 : computePointerICmp(const DataLayout &DL, const TargetLibraryInfo *TLI,
    1904             :                    const DominatorTree *DT, CmpInst::Predicate Pred,
    1905             :                    AssumptionCache *AC, const Instruction *CxtI,
    1906             :                    Value *LHS, Value *RHS) {
    1907             :   // First, skip past any trivial no-ops.
    1908      415446 :   LHS = LHS->stripPointerCasts();
    1909      415446 :   RHS = RHS->stripPointerCasts();
    1910             : 
    1911             :   // A non-null pointer is not equal to a null pointer.
    1912      215205 :   if (llvm::isKnownNonZero(LHS, DL) && isa<ConstantPointerNull>(RHS) &&
    1913         859 :       (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE))
    1914        1718 :     return ConstantInt::get(GetCompareTy(LHS),
    1915        1718 :                             !CmpInst::isTrueWhenEqual(Pred));
    1916             : 
    1917             :   // We can only fold certain predicates on pointer comparisons.
    1918      206864 :   switch (Pred) {
    1919             :   default:
    1920             :     return nullptr;
    1921             : 
    1922             :     // Equality comaprisons are easy to fold.
    1923             :   case CmpInst::ICMP_EQ:
    1924             :   case CmpInst::ICMP_NE:
    1925             :     break;
    1926             : 
    1927             :     // We can only handle unsigned relational comparisons because 'inbounds' on
    1928             :     // a GEP only protects against unsigned wrapping.
    1929        3733 :   case CmpInst::ICMP_UGT:
    1930             :   case CmpInst::ICMP_UGE:
    1931             :   case CmpInst::ICMP_ULT:
    1932             :   case CmpInst::ICMP_ULE:
    1933             :     // However, we have to switch them to their signed variants to handle
    1934             :     // negative indices from the base pointer.
    1935        3733 :     Pred = ICmpInst::getSignedPredicate(Pred);
    1936             :     break;
    1937             :   }
    1938             : 
    1939             :   // Strip off any constant offsets so that we can reason about them.
    1940             :   // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets
    1941             :   // here and compare base addresses like AliasAnalysis does, however there are
    1942             :   // numerous hazards. AliasAnalysis and its utilities rely on special rules
    1943             :   // governing loads and stores which don't apply to icmps. Also, AliasAnalysis
    1944             :   // doesn't need to guarantee pointer inequality when it says NoAlias.
    1945      206853 :   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
    1946      206853 :   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
    1947             : 
    1948             :   // If LHS and RHS are related via constant offsets to the same base
    1949             :   // value, we can replace it with an icmp which just compares the offsets.
    1950      206853 :   if (LHS == RHS)
    1951         118 :     return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
    1952             : 
    1953             :   // Various optimizations for (in)equality comparisons.
    1954      206735 :   if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
    1955             :     // Different non-empty allocations that exist at the same time have
    1956             :     // different addresses (if the program can tell). Global variables always
    1957             :     // exist, so they always exist during the lifetime of each other and all
    1958             :     // allocas. Two different allocas usually have different addresses...
    1959             :     //
    1960             :     // However, if there's an @llvm.stackrestore dynamically in between two
    1961             :     // allocas, they may have the same address. It's tempting to reduce the
    1962             :     // scope of the problem by only looking at *static* allocas here. That would
    1963             :     // cover the majority of allocas while significantly reducing the likelihood
    1964             :     // of having an @llvm.stackrestore pop up in the middle. However, it's not
    1965             :     // actually impossible for an @llvm.stackrestore to pop up in the middle of
    1966             :     // an entry block. Also, if we have a block that's not attached to a
    1967             :     // function, we can't tell if it's "static" under the current definition.
    1968             :     // Theoretically, this problem could be fixed by creating a new kind of
    1969             :     // instruction kind specifically for static allocas. Such a new instruction
    1970             :     // could be required to be at the top of the entry block, thus preventing it
    1971             :     // from being subject to a @llvm.stackrestore. Instcombine could even
    1972             :     // convert regular allocas into these special allocas. It'd be nifty.
    1973             :     // However, until then, this problem remains open.
    1974             :     //
    1975             :     // So, we'll assume that two non-empty allocas have different addresses
    1976             :     // for now.
    1977             :     //
    1978             :     // With all that, if the offsets are within the bounds of their allocations
    1979             :     // (and not one-past-the-end! so we can't use inbounds!), and their
    1980             :     // allocations aren't the same, the pointers are not equal.
    1981             :     //
    1982             :     // Note that it's not necessary to check for LHS being a global variable
    1983             :     // address, due to canonicalization and constant folding.
    1984      203009 :     if (isa<AllocaInst>(LHS) &&
    1985         210 :         (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
    1986          16 :       ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset);
    1987          16 :       ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset);
    1988             :       uint64_t LHSSize, RHSSize;
    1989          32 :       if (LHSOffsetCI && RHSOffsetCI &&
    1990          48 :           getObjectSize(LHS, LHSSize, DL, TLI) &&
    1991          32 :           getObjectSize(RHS, RHSSize, DL, TLI)) {
    1992          16 :         const APInt &LHSOffsetValue = LHSOffsetCI->getValue();
    1993          16 :         const APInt &RHSOffsetValue = RHSOffsetCI->getValue();
    1994          16 :         if (!LHSOffsetValue.isNegative() &&
    1995          16 :             !RHSOffsetValue.isNegative() &&
    1996          48 :             LHSOffsetValue.ult(LHSSize) &&
    1997          16 :             RHSOffsetValue.ult(RHSSize)) {
    1998          32 :           return ConstantInt::get(GetCompareTy(LHS),
    1999          48 :                                   !CmpInst::isTrueWhenEqual(Pred));
    2000             :         }
    2001             :       }
    2002             : 
    2003             :       // Repeat the above check but this time without depending on DataLayout
    2004             :       // or being able to compute a precise size.
    2005           0 :       if (!cast<PointerType>(LHS->getType())->isEmptyTy() &&
    2006           0 :           !cast<PointerType>(RHS->getType())->isEmptyTy() &&
    2007           0 :           LHSOffset->isNullValue() &&
    2008           0 :           RHSOffset->isNullValue())
    2009           0 :         return ConstantInt::get(GetCompareTy(LHS),
    2010           0 :                                 !CmpInst::isTrueWhenEqual(Pred));
    2011             :     }
    2012             : 
    2013             :     // Even if an non-inbounds GEP occurs along the path we can still optimize
    2014             :     // equality comparisons concerning the result. We avoid walking the whole
    2015             :     // chain again by starting where the last calls to
    2016             :     // stripAndComputeConstantOffsets left off and accumulate the offsets.
    2017      202993 :     Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true);
    2018      202993 :     Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true);
    2019      202993 :     if (LHS == RHS)
    2020          14 :       return ConstantExpr::getICmp(Pred,
    2021             :                                    ConstantExpr::getAdd(LHSOffset, LHSNoBound),
    2022          14 :                                    ConstantExpr::getAdd(RHSOffset, RHSNoBound));
    2023             : 
    2024             :     // If one side of the equality comparison must come from a noalias call
    2025             :     // (meaning a system memory allocation function), and the other side must
    2026             :     // come from a pointer that cannot overlap with dynamically-allocated
    2027             :     // memory within the lifetime of the current function (allocas, byval
    2028             :     // arguments, globals), then determine the comparison result here.
    2029      811896 :     SmallVector<Value *, 8> LHSUObjs, RHSUObjs;
    2030      202979 :     GetUnderlyingObjects(LHS, LHSUObjs, DL);
    2031      202979 :     GetUnderlyingObjects(RHS, RHSUObjs, DL);
    2032             : 
    2033             :     // Is the set of underlying objects all noalias calls?
    2034             :     auto IsNAC = [](ArrayRef<Value *> Objects) {
    2035             :       return all_of(Objects, isNoAliasCall);
    2036      405953 :     };
    2037             : 
    2038             :     // Is the set of underlying objects all things which must be disjoint from
    2039             :     // noalias calls. For allocas, we consider only static ones (dynamic
    2040             :     // allocas might be transformed into calls to malloc not simultaneously
    2041             :     // live with the compared-to allocation). For globals, we exclude symbols
    2042             :     // that might be resolve lazily to symbols in another dynamically-loaded
    2043             :     // library (and, thus, could be malloc'ed by the implementation).
    2044             :     auto IsAllocDisjoint = [](ArrayRef<Value *> Objects) {
    2045         900 :       return all_of(Objects, [](Value *V) {
    2046           9 :         if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
    2047           9 :           return AI->getParent() && AI->getFunction() && AI->isStaticAlloca();
    2048           8 :         if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
    2049          20 :           return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() ||
    2050          17 :                   GV->hasProtectedVisibility() || GV->hasGlobalUnnamedAddr()) &&
    2051           6 :                  !GV->isThreadLocal();
    2052          15 :         if (const Argument *A = dyn_cast<Argument>(V))
    2053          15 :           return A->hasByValAttr();
    2054             :         return false;
    2055             :       });
    2056        1792 :     };
    2057             : 
    2058      610024 :     if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
    2059      203674 :         (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
    2060          16 :         return ConstantInt::get(GetCompareTy(LHS),
    2061          26 :                                 !CmpInst::isTrueWhenEqual(Pred));
    2062             : 
    2063             :     // Fold comparisons for non-escaping pointer even if the allocation call
    2064             :     // cannot be elided. We cannot fold malloc comparison to null. Also, the
    2065             :     // dynamic allocation call could be either of the operands.
    2066      202971 :     Value *MI = nullptr;
    2067      203051 :     if (isAllocLikeFn(LHS, TLI) &&
    2068          80 :         llvm::isKnownNonZero(RHS, DL, 0, nullptr, CxtI, DT))
    2069           1 :       MI = LHS;
    2070      203219 :     else if (isAllocLikeFn(RHS, TLI) &&
    2071         249 :              llvm::isKnownNonZero(LHS, DL, 0, nullptr, CxtI, DT))
    2072           8 :       MI = RHS;
    2073             :     // FIXME: We should also fold the compare when the pointer escapes, but the
    2074             :     // compare dominates the pointer escape
    2075           9 :     if (MI && !PointerMayBeCaptured(MI, true, true))
    2076           4 :       return ConstantInt::get(GetCompareTy(LHS),
    2077           4 :                               CmpInst::isFalseWhenEqual(Pred));
    2078             :   }
    2079             : 
    2080             :   // Otherwise, fail.
    2081             :   return nullptr;
    2082             : }
    2083             : 
    2084             : /// Fold an icmp when its operands have i1 scalar type.
    2085      616941 : static Value *simplifyICmpOfBools(CmpInst::Predicate Pred, Value *LHS,
    2086             :                                   Value *RHS, const SimplifyQuery &Q) {
    2087      616941 :   Type *ITy = GetCompareTy(LHS); // The return type.
    2088      616941 :   Type *OpTy = LHS->getType();   // The operand type.
    2089      616941 :   if (!OpTy->isIntOrIntVectorTy(1))
    2090             :     return nullptr;
    2091             : 
    2092             :   // A boolean compared to true/false can be simplified in 14 out of the 20
    2093             :   // (10 predicates * 2 constants) possible combinations. Cases not handled here
    2094             :   // require a 'not' of the LHS, so those must be transformed in InstCombine.
    2095        7999 :   if (match(RHS, m_Zero())) {
    2096             :     switch (Pred) {
    2097             :     case CmpInst::ICMP_NE:  // X !=  0 -> X
    2098             :     case CmpInst::ICMP_UGT: // X >u  0 -> X
    2099             :     case CmpInst::ICMP_SLT: // X <s  0 -> X
    2100             :       return LHS;
    2101             : 
    2102           4 :     case CmpInst::ICMP_ULT: // X <u  0 -> false
    2103             :     case CmpInst::ICMP_SGT: // X >s  0 -> false
    2104           4 :       return getFalse(ITy);
    2105             : 
    2106           3 :     case CmpInst::ICMP_UGE: // X >=u 0 -> true
    2107             :     case CmpInst::ICMP_SLE: // X <=s 0 -> true
    2108           3 :       return getTrue(ITy);
    2109             : 
    2110             :     default: break;
    2111             :     }
    2112         757 :   } else if (match(RHS, m_One())) {
    2113             :     switch (Pred) {
    2114             :     case CmpInst::ICMP_EQ:  // X ==   1 -> X
    2115             :     case CmpInst::ICMP_UGE: // X >=u  1 -> X
    2116             :     case CmpInst::ICMP_SLE: // X <=s -1 -> X
    2117             :       return LHS;
    2118             : 
    2119           4 :     case CmpInst::ICMP_UGT: // X >u   1 -> false
    2120             :     case CmpInst::ICMP_SLT: // X <s  -1 -> false
    2121           4 :       return getFalse(ITy);
    2122             : 
    2123           3 :     case CmpInst::ICMP_ULE: // X <=u  1 -> true
    2124             :     case CmpInst::ICMP_SGE: // X >=s -1 -> true
    2125           3 :       return getTrue(ITy);
    2126             : 
    2127             :     default: break;
    2128             :     }
    2129             :   }
    2130             : 
    2131         635 :   switch (Pred) {
    2132             :   default:
    2133             :     break;
    2134          21 :   case ICmpInst::ICMP_UGE:
    2135          63 :     if (isImpliedCondition(RHS, LHS, Q.DL).getValueOr(false))
    2136           1 :       return getTrue(ITy);
    2137             :     break;
    2138          23 :   case ICmpInst::ICMP_SGE:
    2139             :     /// For signed comparison, the values for an i1 are 0 and -1
    2140             :     /// respectively. This maps into a truth table of:
    2141             :     /// LHS | RHS | LHS >=s RHS   | LHS implies RHS
    2142             :     ///  0  |  0  |  1 (0 >= 0)   |  1
    2143             :     ///  0  |  1  |  1 (0 >= -1)  |  1
    2144             :     ///  1  |  0  |  0 (-1 >= 0)  |  0
    2145             :     ///  1  |  1  |  1 (-1 >= -1) |  1
    2146          69 :     if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
    2147           1 :       return getTrue(ITy);
    2148             :     break;
    2149          37 :   case ICmpInst::ICMP_ULE:
    2150         111 :     if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
    2151           8 :       return getTrue(ITy);
    2152             :     break;
    2153             :   }
    2154             : 
    2155             :   return nullptr;
    2156             : }
    2157             : 
    2158             : /// Try hard to fold icmp with zero RHS because this is a common case.
    2159      613321 : static Value *simplifyICmpWithZero(CmpInst::Predicate Pred, Value *LHS,
    2160             :                                    Value *RHS, const SimplifyQuery &Q) {
    2161     1071166 :   if (!match(RHS, m_Zero()))
    2162             :     return nullptr;
    2163             : 
    2164      315698 :   Type *ITy = GetCompareTy(LHS); // The return type.
    2165      315698 :   switch (Pred) {
    2166           0 :   default:
    2167           0 :     llvm_unreachable("Unknown ICmp predicate!");
    2168          89 :   case ICmpInst::ICMP_ULT:
    2169          89 :     return getFalse(ITy);
    2170         133 :   case ICmpInst::ICMP_UGE:
    2171         133 :     return getTrue(ITy);
    2172      130487 :   case ICmpInst::ICMP_EQ:
    2173             :   case ICmpInst::ICMP_ULE:
    2174      130487 :     if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
    2175         919 :       return getFalse(ITy);
    2176             :     break;
    2177      175864 :   case ICmpInst::ICMP_NE:
    2178             :   case ICmpInst::ICMP_UGT:
    2179      175864 :     if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
    2180        1532 :       return getTrue(ITy);
    2181             :     break;
    2182        2626 :   case ICmpInst::ICMP_SLT: {
    2183        2626 :     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2184        2626 :     if (LHSKnown.isNegative())
    2185          12 :       return getTrue(ITy);
    2186        2623 :     if (LHSKnown.isNonNegative())
    2187           6 :       return getFalse(ITy);
    2188        2617 :     break;
    2189             :   }
    2190          54 :   case ICmpInst::ICMP_SLE: {
    2191          54 :     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2192          54 :     if (LHSKnown.isNegative())
    2193           0 :       return getTrue(ITy);
    2194          56 :     if (LHSKnown.isNonNegative() &&
    2195           2 :         isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
    2196           0 :       return getFalse(ITy);
    2197          54 :     break;
    2198             :   }
    2199         270 :   case ICmpInst::ICMP_SGE: {
    2200         270 :     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2201         270 :     if (LHSKnown.isNegative())
    2202           2 :       return getFalse(ITy);
    2203         270 :     if (LHSKnown.isNonNegative())
    2204           2 :       return getTrue(ITy);
    2205         268 :     break;
    2206             :   }
    2207        6175 :   case ICmpInst::ICMP_SGT: {
    2208        6175 :     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2209        6175 :     if (LHSKnown.isNegative())
    2210           6 :       return getFalse(ITy);
    2211        6259 :     if (LHSKnown.isNonNegative() &&
    2212          85 :         isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
    2213           4 :       return getTrue(ITy);
    2214        6170 :     break;
    2215             :   }
    2216             :   }
    2217             : 
    2218             :   return nullptr;
    2219             : }
    2220             : 
    2221             : /// Many binary operators with a constant operand have an easy-to-compute
    2222             : /// range of outputs. This can be used to fold a comparison to always true or
    2223             : /// always false.
    2224       74897 : static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper) {
    2225       74897 :   unsigned Width = Lower.getBitWidth();
    2226             :   const APInt *C;
    2227       74897 :   switch (BO.getOpcode()) {
    2228       35938 :   case Instruction::Add:
    2229      143754 :     if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) {
    2230             :       // FIXME: If we have both nuw and nsw, we should reduce the range further.
    2231       33174 :       if (BO.hasNoUnsignedWrap()) {
    2232             :         // 'add nuw x, C' produces [C, UINT_MAX].
    2233       15635 :         Lower = *C;
    2234       17539 :       } else if (BO.hasNoSignedWrap()) {
    2235        7692 :         if (C->isNegative()) {
    2236             :           // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
    2237        3636 :           Lower = APInt::getSignedMinValue(Width);
    2238        8484 :           Upper = APInt::getSignedMaxValue(Width) + *C + 1;
    2239             :         } else {
    2240             :           // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX].
    2241       13170 :           Lower = APInt::getSignedMinValue(Width) + *C;
    2242       13170 :           Upper = APInt::getSignedMaxValue(Width) + 1;
    2243             :         }
    2244             :       }
    2245             :     }
    2246             :     break;
    2247             : 
    2248       16409 :   case Instruction::And:
    2249       49227 :     if (match(BO.getOperand(1), m_APInt(C)))
    2250             :       // 'and x, C' produces [0, C].
    2251       61692 :       Upper = *C + 1;
    2252             :     break;
    2253             : 
    2254         862 :   case Instruction::Or:
    2255        2586 :     if (match(BO.getOperand(1), m_APInt(C)))
    2256             :       // 'or x, C' produces [C, UINT_MAX].
    2257         559 :       Lower = *C;
    2258             :     break;
    2259             : 
    2260        5672 :   case Instruction::AShr:
    2261       22646 :     if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
    2262             :       // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C].
    2263       22520 :       Lower = APInt::getSignedMinValue(Width).ashr(*C);
    2264       33780 :       Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1;
    2265         126 :     } else if (match(BO.getOperand(0), m_APInt(C))) {
    2266          36 :       unsigned ShiftAmount = Width - 1;
    2267          72 :       if (!C->isNullValue() && BO.isExact())
    2268          16 :         ShiftAmount = C->countTrailingZeros();
    2269          72 :       if (C->isNegative()) {
    2270             :         // 'ashr C, x' produces [C, C >> (Width-1)]
    2271          35 :         Lower = *C;
    2272         175 :         Upper = C->ashr(ShiftAmount) + 1;
    2273             :       } else {
    2274             :         // 'ashr C, x' produces [C >> (Width-1), C]
    2275           3 :         Lower = C->ashr(ShiftAmount);
    2276           6 :         Upper = *C + 1;
    2277             :       }
    2278             :     }
    2279             :     break;
    2280             : 
    2281        1657 :   case Instruction::LShr:
    2282        6586 :     if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
    2283             :       // 'lshr x, C' produces [0, UINT_MAX >> C].
    2284        9690 :       Upper = APInt::getAllOnesValue(Width).lshr(*C) + 1;
    2285         126 :     } else if (match(BO.getOperand(0), m_APInt(C))) {
    2286             :       // 'lshr C, x' produces [C >> (Width-1), C].
    2287          37 :       unsigned ShiftAmount = Width - 1;
    2288          74 :       if (!C->isNullValue() && BO.isExact())
    2289          16 :         ShiftAmount = C->countTrailingZeros();
    2290         111 :       Lower = C->lshr(ShiftAmount);
    2291         222 :       Upper = *C + 1;
    2292             :     }
    2293             :     break;
    2294             : 
    2295        1379 :   case Instruction::Shl:
    2296        4137 :     if (match(BO.getOperand(0), m_APInt(C))) {
    2297          52 :       if (BO.hasNoUnsignedWrap()) {
    2298             :         // 'shl nuw C, x' produces [C, C << CLZ(C)]
    2299           3 :         Lower = *C;
    2300          15 :         Upper = Lower.shl(Lower.countLeadingZeros()) + 1;
    2301          49 :       } else if (BO.hasNoSignedWrap()) { // TODO: What if both nuw+nsw?
    2302          16 :         if (C->isNegative()) {
    2303             :           // 'shl nsw C, x' produces [C << CLO(C)-1, C]
    2304           6 :           unsigned ShiftAmount = C->countLeadingOnes() - 1;
    2305          18 :           Lower = C->shl(ShiftAmount);
    2306          36 :           Upper = *C + 1;
    2307             :         } else {
    2308             :           // 'shl nsw C, x' produces [C, C << CLZ(C)-1]
    2309           2 :           unsigned ShiftAmount = C->countLeadingZeros() - 1;
    2310           2 :           Lower = *C;
    2311          10 :           Upper = C->shl(ShiftAmount) + 1;
    2312             :         }
    2313             :       }
    2314             :     }
    2315             :     break;
    2316             : 
    2317         724 :   case Instruction::SDiv:
    2318        2172 :     if (match(BO.getOperand(1), m_APInt(C))) {
    2319        1442 :       APInt IntMin = APInt::getSignedMinValue(Width);
    2320        1442 :       APInt IntMax = APInt::getSignedMaxValue(Width);
    2321        1442 :       if (C->isAllOnesValue()) {
    2322             :         // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX]
    2323             :         //    where C != -1 and C != 0 and C != 1
    2324           5 :         Lower = IntMin + 1;
    2325           5 :         Upper = IntMax + 1;
    2326         720 :       } else if (C->countLeadingZeros() < Width - 1) {
    2327             :         // 'sdiv x, C' produces [INT_MIN / C, INT_MAX / C]
    2328             :         //    where C != -1 and C != 0 and C != 1
    2329        2160 :         Lower = IntMin.sdiv(*C);
    2330        2160 :         Upper = IntMax.sdiv(*C);
    2331         720 :         if (Lower.sgt(Upper))
    2332             :           std::swap(Lower, Upper);
    2333        3600 :         Upper = Upper + 1;
    2334             :         assert(Upper != Lower && "Upper part of range has wrapped!");
    2335             :       }
    2336           9 :     } else if (match(BO.getOperand(0), m_APInt(C))) {
    2337           3 :       if (C->isMinSignedValue()) {
    2338             :         // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2].
    2339           1 :         Lower = *C;
    2340           5 :         Upper = Lower.lshr(1) + 1;
    2341             :       } else {
    2342             :         // 'sdiv C, x' produces [-|C|, |C|].
    2343          10 :         Upper = C->abs() + 1;
    2344          14 :         Lower = (-Upper) + 1;
    2345             :       }
    2346             :     }
    2347             :     break;
    2348             : 
    2349         908 :   case Instruction::UDiv:
    2350        3582 :     if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) {
    2351             :       // 'udiv x, C' produces [0, UINT_MAX / C].
    2352        2574 :       Upper = APInt::getMaxValue(Width).udiv(*C) + 1;
    2353        1437 :     } else if (match(BO.getOperand(0), m_APInt(C))) {
    2354             :       // 'udiv C, x' produces [0, C].
    2355        2064 :       Upper = *C + 1;
    2356             :     }
    2357             :     break;
    2358             : 
    2359          65 :   case Instruction::SRem:
    2360         195 :     if (match(BO.getOperand(1), m_APInt(C))) {
    2361             :       // 'srem x, C' produces (-|C|, |C|).
    2362          63 :       Upper = C->abs();
    2363         147 :       Lower = (-Upper) + 1;
    2364             :     }
    2365             :     break;
    2366             : 
    2367         463 :   case Instruction::URem:
    2368        1389 :     if (match(BO.getOperand(1), m_APInt(C)))
    2369             :       // 'urem x, C' produces [0, C).
    2370         286 :       Upper = *C;
    2371             :     break;
    2372             : 
    2373             :   default:
    2374             :     break;
    2375             :   }
    2376       74897 : }
    2377             : 
    2378      610632 : static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
    2379             :                                        Value *RHS) {
    2380             :   const APInt *C;
    2381     1221264 :   if (!match(RHS, m_APInt(C)))
    2382             :     return nullptr;
    2383             : 
    2384             :   // Rule out tautological comparisons (eg., ult 0 or uge 0).
    2385      581804 :   ConstantRange RHS_CR = ConstantRange::makeExactICmpRegion(Pred, *C);
    2386      290902 :   if (RHS_CR.isEmptySet())
    2387          87 :     return ConstantInt::getFalse(GetCompareTy(RHS));
    2388      290815 :   if (RHS_CR.isFullSet())
    2389           5 :     return ConstantInt::getTrue(GetCompareTy(RHS));
    2390             : 
    2391             :   // Find the range of possible values for binary operators.
    2392      290810 :   unsigned Width = C->getBitWidth();
    2393      290810 :   APInt Lower = APInt(Width, 0);
    2394      581620 :   APInt Upper = APInt(Width, 0);
    2395       74897 :   if (auto *BO = dyn_cast<BinaryOperator>(LHS))
    2396       74897 :     setLimitsForBinOp(*BO, Lower, Upper);
    2397             : 
    2398             :   ConstantRange LHS_CR =
    2399     1493503 :       Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true);
    2400             : 
    2401      258626 :   if (auto *I = dyn_cast<Instruction>(LHS))
    2402      198615 :     if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
    2403       38454 :       LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges));
    2404             : 
    2405      290810 :   if (!LHS_CR.isFullSet()) {
    2406       77907 :     if (RHS_CR.contains(LHS_CR))
    2407         253 :       return ConstantInt::getTrue(GetCompareTy(RHS));
    2408       77654 :     if (RHS_CR.inverse().contains(LHS_CR))
    2409         352 :       return ConstantInt::getFalse(GetCompareTy(RHS));
    2410             :   }
    2411             : 
    2412             :   return nullptr;
    2413             : }
    2414             : 
    2415             : /// TODO: A large part of this logic is duplicated in InstCombine's
    2416             : /// foldICmpBinOp(). We should be able to share that and avoid the code
    2417             : /// duplication.
    2418      605804 : static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
    2419             :                                     Value *RHS, const SimplifyQuery &Q,
    2420             :                                     unsigned MaxRecurse) {
    2421      605804 :   Type *ITy = GetCompareTy(LHS); // The return type.
    2422             : 
    2423      605804 :   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
    2424      605804 :   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
    2425      605804 :   if (MaxRecurse && (LBO || RBO)) {
    2426             :     // Analyze the case when either LHS or RHS is an add instruction.
    2427      113451 :     Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
    2428             :     // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
    2429      113451 :     bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
    2430      214795 :     if (LBO && LBO->getOpcode() == Instruction::Add) {
    2431       48618 :       A = LBO->getOperand(0);
    2432       48618 :       B = LBO->getOperand(1);
    2433             :       NoLHSWrapProblem =
    2434       83314 :           ICmpInst::isEquality(Pred) ||
    2435      101732 :           (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
    2436       26416 :           (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
    2437             :     }
    2438      133450 :     if (RBO && RBO->getOpcode() == Instruction::Add) {
    2439        8456 :       C = RBO->getOperand(0);
    2440        8456 :       D = RBO->getOperand(1);
    2441             :       NoRHSWrapProblem =
    2442       11321 :           ICmpInst::isEquality(Pred) ||
    2443       13837 :           (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
    2444        2590 :           (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
    2445             :     }
    2446             : 
    2447             :     // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
    2448      113451 :     if ((A == RHS || B == RHS) && NoLHSWrapProblem)
    2449         858 :       if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
    2450         286 :                                       Constant::getNullValue(RHS->getType()), Q,
    2451         286 :                                       MaxRecurse - 1))
    2452             :         return V;
    2453             : 
    2454             :     // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
    2455      113448 :     if ((C == LHS || D == LHS) && NoRHSWrapProblem)
    2456           2 :       if (Value *V =
    2457           2 :               SimplifyICmpInst(Pred, Constant::getNullValue(LHS->getType()),
    2458           2 :                                C == LHS ? D : C, Q, MaxRecurse - 1))
    2459             :         return V;
    2460             : 
    2461             :     // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
    2462      113446 :     if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem &&
    2463             :         NoRHSWrapProblem) {
    2464             :       // Determine Y and Z in the form icmp (X+Y), (X+Z).
    2465             :       Value *Y, *Z;
    2466          12 :       if (A == C) {
    2467             :         // C + B == C + D  ->  B == D
    2468             :         Y = B;
    2469             :         Z = D;
    2470           9 :       } else if (A == D) {
    2471             :         // D + B == C + D  ->  B == C
    2472             :         Y = B;
    2473             :         Z = C;
    2474           7 :       } else if (B == C) {
    2475             :         // A + C == C + D  ->  A == D
    2476             :         Y = A;
    2477             :         Z = D;
    2478             :       } else {
    2479             :         assert(B == D);
    2480             :         // A + D == C + D  ->  A == C
    2481           7 :         Y = A;
    2482           7 :         Z = C;
    2483             :       }
    2484          12 :       if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse - 1))
    2485             :         return V;
    2486             :     }
    2487             :   }
    2488             : 
    2489             :   {
    2490      605794 :     Value *Y = nullptr;
    2491             :     // icmp pred (or X, Y), X
    2492     1012598 :     if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
    2493         956 :       if (Pred == ICmpInst::ICMP_ULT)
    2494           2 :         return getFalse(ITy);
    2495         955 :       if (Pred == ICmpInst::ICMP_UGE)
    2496           1 :         return getTrue(ITy);
    2497             : 
    2498         954 :       if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
    2499         200 :         KnownBits RHSKnown = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2500         200 :         KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2501         152 :         if (RHSKnown.isNonNegative() && YKnown.isNegative())
    2502          16 :           return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
    2503         202 :         if (RHSKnown.isNegative() || YKnown.isNonNegative())
    2504          20 :           return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
    2505             :       }
    2506             :     }
    2507             :     // icmp pred X, (or X, Y)
    2508      685724 :     if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) {
    2509         108 :       if (Pred == ICmpInst::ICMP_ULE)
    2510           1 :         return getTrue(ITy);
    2511         107 :       if (Pred == ICmpInst::ICMP_UGT)
    2512           1 :         return getFalse(ITy);
    2513             : 
    2514         106 :       if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) {
    2515         200 :         KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2516         200 :         KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2517         152 :         if (LHSKnown.isNonNegative() && YKnown.isNegative())
    2518          16 :           return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy);
    2519         202 :         if (LHSKnown.isNegative() || YKnown.isNonNegative())
    2520          20 :           return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy);
    2521             :       }
    2522             :     }
    2523             :   }
    2524             : 
    2525             :   // icmp pred (and X, Y), X
    2526      910797 :   if (LBO && match(LBO, m_c_And(m_Value(), m_Specific(RHS)))) {
    2527        2128 :     if (Pred == ICmpInst::ICMP_UGT)
    2528           1 :       return getFalse(ITy);
    2529        2127 :     if (Pred == ICmpInst::ICMP_ULE)
    2530           1 :       return getTrue(ITy);
    2531             :   }
    2532             :   // icmp pred X, (and X, Y)
    2533      665680 :   if (RBO && match(RBO, m_c_And(m_Value(), m_Specific(LHS)))) {
    2534         132 :     if (Pred == ICmpInst::ICMP_UGE)
    2535           1 :       return getTrue(ITy);
    2536         131 :     if (Pred == ICmpInst::ICMP_ULT)
    2537           1 :       return getFalse(ITy);
    2538             :   }
    2539             : 
    2540             :   // 0 - (zext X) pred C
    2541     2047010 :   if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
    2542           6 :     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
    2543           6 :       if (RHSC->getValue().isStrictlyPositive()) {
    2544           4 :         if (Pred == ICmpInst::ICMP_SLT)
    2545           1 :           return ConstantInt::getTrue(RHSC->getContext());
    2546           3 :         if (Pred == ICmpInst::ICMP_SGE)
    2547           1 :           return ConstantInt::getFalse(RHSC->getContext());
    2548           2 :         if (Pred == ICmpInst::ICMP_EQ)
    2549           1 :           return ConstantInt::getFalse(RHSC->getContext());
    2550           1 :         if (Pred == ICmpInst::ICMP_NE)
    2551           1 :           return ConstantInt::getTrue(RHSC->getContext());
    2552             :       }
    2553           4 :       if (RHSC->getValue().isNonNegative()) {
    2554           2 :         if (Pred == ICmpInst::ICMP_SLE)
    2555           1 :           return ConstantInt::getTrue(RHSC->getContext());
    2556           1 :         if (Pred == ICmpInst::ICMP_SGT)
    2557           1 :           return ConstantInt::getFalse(RHSC->getContext());
    2558             :       }
    2559             :     }
    2560             :   }
    2561             : 
    2562             :   // icmp pred (urem X, Y), Y
    2563      910763 :   if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
    2564          38 :     switch (Pred) {
    2565             :     default:
    2566             :       break;
    2567           1 :     case ICmpInst::ICMP_SGT:
    2568             :     case ICmpInst::ICMP_SGE: {
    2569           1 :       KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2570           1 :       if (!Known.isNonNegative())
    2571             :         break;
    2572             :       LLVM_FALLTHROUGH;
    2573             :     }
    2574             :     case ICmpInst::ICMP_EQ:
    2575             :     case ICmpInst::ICMP_UGT:
    2576             :     case ICmpInst::ICMP_UGE:
    2577          13 :       return getFalse(ITy);
    2578           1 :     case ICmpInst::ICMP_SLT:
    2579             :     case ICmpInst::ICMP_SLE: {
    2580           1 :       KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2581           1 :       if (!Known.isNonNegative())
    2582             :         break;
    2583             :       LLVM_FALLTHROUGH;
    2584             :     }
    2585             :     case ICmpInst::ICMP_NE:
    2586             :     case ICmpInst::ICMP_ULT:
    2587             :     case ICmpInst::ICMP_ULE:
    2588          23 :       return getTrue(ITy);
    2589             :     }
    2590             :   }
    2591             : 
    2592             :   // icmp pred X, (urem Y, X)
    2593      665630 :   if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
    2594           1 :     switch (Pred) {
    2595             :     default:
    2596             :       break;
    2597           0 :     case ICmpInst::ICMP_SGT:
    2598             :     case ICmpInst::ICMP_SGE: {
    2599           0 :       KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2600           0 :       if (!Known.isNonNegative())
    2601             :         break;
    2602             :       LLVM_FALLTHROUGH;
    2603             :     }
    2604             :     case ICmpInst::ICMP_NE:
    2605             :     case ICmpInst::ICMP_UGT:
    2606             :     case ICmpInst::ICMP_UGE:
    2607           1 :       return getTrue(ITy);
    2608           0 :     case ICmpInst::ICMP_SLT:
    2609             :     case ICmpInst::ICMP_SLE: {
    2610           0 :       KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
    2611           0 :       if (!Known.isNonNegative())
    2612             :         break;
    2613             :       LLVM_FALLTHROUGH;
    2614             :     }
    2615             :     case ICmpInst::ICMP_EQ:
    2616             :     case ICmpInst::ICMP_ULT:
    2617             :     case ICmpInst::ICMP_ULE:
    2618           0 :       return getFalse(ITy);
    2619             :     }
    2620             :   }
    2621             : 
    2622             :   // x >> y <=u x
    2623             :   // x udiv y <=u x.
    2624     1617964 :   if (LBO && (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
    2625     1012227 :               match(LBO, m_UDiv(m_Specific(RHS), m_Value())))) {
    2626             :     // icmp pred (X op Y), X
    2627          10 :     if (Pred == ICmpInst::ICMP_UGT)
    2628           2 :       return getFalse(ITy);
    2629           8 :     if (Pred == ICmpInst::ICMP_ULE)
    2630           2 :       return getTrue(ITy);
    2631             :   }
    2632             : 
    2633             :   // x >=u x >> y
    2634             :   // x >=u x udiv y.
    2635     1291304 :   if (RBO && (match(RBO, m_LShr(m_Specific(LHS), m_Value())) ||
    2636      685583 :               match(RBO, m_UDiv(m_Specific(LHS), m_Value())))) {
    2637             :     // icmp pred X, (X op Y)
    2638           4 :     if (Pred == ICmpInst::ICMP_ULT)
    2639           2 :       return getFalse(ITy);
    2640           2 :     if (Pred == ICmpInst::ICMP_UGE)
    2641           2 :       return getTrue(ITy);
    2642             :   }
    2643             : 
    2644             :   // handle:
    2645             :   //   CI2 << X == CI
    2646             :   //   CI2 << X != CI
    2647             :   //
    2648             :   //   where CI2 is a power of 2 and CI isn't
    2649      283872 :   if (auto *CI = dyn_cast<ConstantInt>(RHS)) {
    2650      283872 :     const APInt *CI2Val, *CIVal = &CI->getValue();
    2651      505195 :     if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) &&
    2652          28 :         CI2Val->isPowerOf2()) {
    2653          22 :       if (!CIVal->isPowerOf2()) {
    2654             :         // CI2 << X can equal zero in some circumstances,
    2655             :         // this simplification is unsafe if CI is zero.
    2656             :         //
    2657             :         // We know it is safe if:
    2658             :         // - The shift is nsw, we can't shift out the one bit.
    2659             :         // - The shift is nuw, we can't shift out the one bit.
    2660             :         // - CI2 is one
    2661             :         // - CI isn't zero
    2662          38 :         if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() ||
    2663          38 :             CI2Val->isOneValue() || !CI->isZero()) {
    2664          12 :           if (Pred == ICmpInst::ICMP_EQ)
    2665           7 :             return ConstantInt::getFalse(RHS->getContext());
    2666          10 :           if (Pred == ICmpInst::ICMP_NE)
    2667           1 :             return ConstantInt::getTrue(RHS->getContext());
    2668             :         }
    2669             :       }
    2670          23 :       if (CIVal->isSignMask() && CI2Val->isOneValue()) {
    2671           4 :         if (Pred == ICmpInst::ICMP_UGT)
    2672           1 :           return ConstantInt::getFalse(RHS->getContext());
    2673           3 :         if (Pred == ICmpInst::ICMP_ULE)
    2674           1 :           return ConstantInt::getTrue(RHS->getContext());
    2675             :       }
    2676             :     }
    2677             :   }
    2678             : 
    2679      624119 :   if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
    2680        5358 :       LBO->getOperand(1) == RBO->getOperand(1)) {
    2681         601 :     switch (LBO->getOpcode()) {
    2682             :     default:
    2683             :       break;
    2684          85 :     case Instruction::UDiv:
    2685             :     case Instruction::LShr:
    2686          85 :       if (ICmpInst::isSigned(Pred) || !LBO->isExact() || !RBO->isExact())
    2687             :         break;
    2688           4 :       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
    2689           1 :                                       RBO->getOperand(0), Q, MaxRecurse - 1))
    2690           0 :           return V;
    2691             :       break;
    2692         149 :     case Instruction::SDiv:
    2693         149 :       if (!ICmpInst::isEquality(Pred) || !LBO->isExact() || !RBO->isExact())
    2694             :         break;
    2695           8 :       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
    2696           2 :                                       RBO->getOperand(0), Q, MaxRecurse - 1))
    2697           1 :         return V;
    2698             :       break;
    2699         146 :     case Instruction::AShr:
    2700         146 :       if (!LBO->isExact() || !RBO->isExact())
    2701             :         break;
    2702         580 :       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
    2703         145 :                                       RBO->getOperand(0), Q, MaxRecurse - 1))
    2704         145 :         return V;
    2705             :       break;
    2706           3 :     case Instruction::Shl: {
    2707           3 :       bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
    2708           3 :       bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
    2709           3 :       if (!NUW && !NSW)
    2710             :         break;
    2711           0 :       if (!NSW && ICmpInst::isSigned(Pred))
    2712             :         break;
    2713           0 :       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
    2714           0 :                                       RBO->getOperand(0), Q, MaxRecurse - 1))
    2715             :         return V;
    2716             :       break;
    2717             :     }
    2718             :     }
    2719             :   }
    2720             :   return nullptr;
    2721             : }
    2722             : 
    2723             : /// Simplify integer comparisons where at least one operand of the compare
    2724             : /// matches an integer min/max idiom.
    2725      605704 : static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS,
    2726             :                                      Value *RHS, const SimplifyQuery &Q,
    2727             :                                      unsigned MaxRecurse) {
    2728      605704 :   Type *ITy = GetCompareTy(LHS); // The return type.
    2729             :   Value *A, *B;
    2730      605704 :   CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
    2731             :   CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
    2732             : 
    2733             :   // Signed variants on "max(a,b)>=a -> true".
    2734     2422816 :   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
    2735         104 :     if (A != RHS)
    2736             :       std::swap(A, B);       // smax(A, B) pred A.
    2737             :     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
    2738             :     // We analyze this as smax(A, B) pred A.
    2739             :     P = Pred;
    2740     3028103 :   } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
    2741         217 :              (A == LHS || B == LHS)) {
    2742          11 :     if (A != LHS)
    2743             :       std::swap(A, B);       // A pred smax(A, B).
    2744          11 :     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
    2745             :     // We analyze this as smax(A, B) swapped-pred A.
    2746          11 :     P = CmpInst::getSwappedPredicate(Pred);
    2747     3028568 :   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
    2748        1256 :              (A == RHS || B == RHS)) {
    2749          19 :     if (A != RHS)
    2750             :       std::swap(A, B);       // smin(A, B) pred A.
    2751          19 :     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
    2752             :     // We analyze this as smax(-A, -B) swapped-pred -A.
    2753             :     // Note that we do not need to actually form -A or -B thanks to EqP.
    2754          19 :     P = CmpInst::getSwappedPredicate(Pred);
    2755     3028327 :   } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
    2756        1040 :              (A == LHS || B == LHS)) {
    2757          68 :     if (A != LHS)
    2758             :       std::swap(A, B);       // A pred smin(A, B).
    2759             :     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
    2760             :     // We analyze this as smax(-A, -B) pred -A.
    2761             :     // Note that we do not need to actually form -A or -B thanks to EqP.
    2762             :     P = Pred;
    2763             :   }
    2764         202 :   if (P != CmpInst::BAD_ICMP_PREDICATE) {
    2765             :     // Cases correspond to "max(A, B) p A".
    2766         202 :     switch (P) {
    2767             :     default:
    2768             :       break;
    2769          18 :     case CmpInst::ICMP_EQ:
    2770             :     case CmpInst::ICMP_SLE:
    2771             :       // Equivalent to "A EqP B".  This may be the same as the condition tested
    2772             :       // in the max/min; if so, we can just return that.
    2773          18 :       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
    2774          17 :         return V;
    2775          17 :       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
    2776          16 :         return V;
    2777             :       // Otherwise, see if "A EqP B" simplifies.
    2778          16 :       if (MaxRecurse)
    2779          16 :         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
    2780             :           return V;
    2781             :       break;
    2782          74 :     case CmpInst::ICMP_NE:
    2783             :     case CmpInst::ICMP_SGT: {
    2784          74 :       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
    2785             :       // Equivalent to "A InvEqP B".  This may be the same as the condition
    2786             :       // tested in the max/min; if so, we can just return that.
    2787          74 :       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
    2788             :         return V;
    2789          69 :       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
    2790             :         return V;
    2791             :       // Otherwise, see if "A InvEqP B" simplifies.
    2792          47 :       if (MaxRecurse)
    2793          47 :         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
    2794             :           return V;
    2795             :       break;
    2796             :     }
    2797           8 :     case CmpInst::ICMP_SGE:
    2798             :       // Always true.
    2799           8 :       return getTrue(ITy);
    2800         102 :     case CmpInst::ICMP_SLT:
    2801             :       // Always false.
    2802         102 :       return getFalse(ITy);
    2803             :     }
    2804             :   }
    2805             : 
    2806             :   // Unsigned variants on "max(a,b)>=a -> true".
    2807      605565 :   P = CmpInst::BAD_ICMP_PREDICATE;
    2808     2422264 :   if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
    2809         126 :     if (A != RHS)
    2810             :       std::swap(A, B);       // umax(A, B) pred A.
    2811             :     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
    2812             :     // We analyze this as umax(A, B) pred A.
    2813             :     P = Pred;
    2814     3027285 :   } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
    2815         191 :              (A == LHS || B == LHS)) {
    2816          11 :     if (A != LHS)
    2817             :       std::swap(A, B);       // A pred umax(A, B).
    2818          11 :     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
    2819             :     // We analyze this as umax(A, B) swapped-pred A.
    2820          11 :     P = CmpInst::getSwappedPredicate(Pred);
    2821     3028261 :   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
    2822        2249 :              (A == RHS || B == RHS)) {
    2823          12 :     if (A != RHS)
    2824             :       std::swap(A, B);       // umin(A, B) pred A.
    2825          12 :     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
    2826             :     // We analyze this as umax(-A, -B) swapped-pred -A.
    2827             :     // Note that we do not need to actually form -A or -B thanks to EqP.
    2828          12 :     P = CmpInst::getSwappedPredicate(Pred);
    2829     3028025 :   } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
    2830        1972 :              (A == LHS || B == LHS)) {
    2831          64 :     if (A != LHS)
    2832             :       std::swap(A, B);       // A pred umin(A, B).
    2833             :     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
    2834             :     // We analyze this as umax(-A, -B) pred -A.
    2835             :     // Note that we do not need to actually form -A or -B thanks to EqP.
    2836             :     P = Pred;
    2837             :   }
    2838         213 :   if (P != CmpInst::BAD_ICMP_PREDICATE) {
    2839             :     // Cases correspond to "max(A, B) p A".
    2840         213 :     switch (P) {
    2841             :     default:
    2842             :       break;
    2843          19 :     case CmpInst::ICMP_EQ:
    2844             :     case CmpInst::ICMP_ULE:
    2845             :       // Equivalent to "A EqP B".  This may be the same as the condition tested
    2846             :       // in the max/min; if so, we can just return that.
    2847          19 :       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
    2848          18 :         return V;
    2849          18 :       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
    2850          17 :         return V;
    2851             :       // Otherwise, see if "A EqP B" simplifies.
    2852          17 :       if (MaxRecurse)
    2853          17 :         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
    2854             :           return V;
    2855             :       break;
    2856          71 :     case CmpInst::ICMP_NE:
    2857             :     case CmpInst::ICMP_UGT: {
    2858          71 :       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
    2859             :       // Equivalent to "A InvEqP B".  This may be the same as the condition
    2860             :       // tested in the max/min; if so, we can just return that.
    2861          71 :       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
    2862             :         return V;
    2863          67 :       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
    2864             :         return V;
    2865             :       // Otherwise, see if "A InvEqP B" simplifies.
    2866          45 :       if (MaxRecurse)
    2867          45 :         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
    2868             :           return V;
    2869             :       break;
    2870             :     }
    2871           4 :     case CmpInst::ICMP_UGE:
    2872             :       // Always true.
    2873           4 :       return getTrue(ITy);
    2874         119 :     case CmpInst::ICMP_ULT:
    2875             :       // Always false.
    2876         119 :       return getFalse(ITy);
    2877             :     }
    2878             :   }
    2879             : 
    2880             :   // Variants on "max(x,y) >= min(x,z)".
    2881             :   Value *C, *D;
    2882     3027877 :   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
    2883     1214056 :       match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
    2884          38 :       (A == C || A == D || B == C || B == D)) {
    2885             :     // max(x, ?) pred min(x, ?).
    2886          38 :     if (Pred == CmpInst::ICMP_SGE)
    2887             :       // Always true.
    2888           1 :       return getTrue(ITy);
    2889          37 :     if (Pred == CmpInst::ICMP_SLT)
    2890             :       // Always false.
    2891           1 :       return getFalse(ITy);
    2892     3027500 :   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
    2893     1213232 :              match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
    2894           2 :              (A == C || A == D || B == C || B == D)) {
    2895             :     // min(x, ?) pred max(x, ?).
    2896           2 :     if (Pred == CmpInst::ICMP_SLE)
    2897             :       // Always true.
    2898           1 :       return getTrue(ITy);
    2899           1 :     if (Pred == CmpInst::ICMP_SGT)
    2900             :       // Always false.
    2901           1 :       return getFalse(ITy);
    2902     3027675 :   } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
    2903     1213968 :              match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
    2904          38 :              (A == C || A == D || B == C || B == D)) {
    2905             :     // max(x, ?) pred min(x, ?).
    2906          38 :     if (Pred == CmpInst::ICMP_UGE)
    2907             :       // Always true.
    2908           1 :       return getTrue(ITy);
    2909          37 :     if (Pred == CmpInst::ICMP_ULT)
    2910             :       // Always false.
    2911           1 :       return getFalse(ITy);
    2912     3027803 :   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
    2913     1215164 :              match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
    2914           2 :              (A == C || A == D || B == C || B == D)) {
    2915             :     // min(x, ?) pred max(x, ?).
    2916           2 :     if (Pred == CmpInst::ICMP_ULE)
    2917             :       // Always true.
    2918           1 :       return getTrue(ITy);
    2919           1 :     if (Pred == CmpInst::ICMP_UGT)
    2920             :       // Always false.
    2921           1 :       return getFalse(ITy);
    2922             :   }
    2923             : 
    2924             :   return nullptr;
    2925             : }
    2926             : 
    2927             : /// Given operands for an ICmpInst, see if we can fold the result.
    2928             : /// If not, this returns null.
    2929      662713 : static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
    2930             :                                const SimplifyQuery &Q, unsigned MaxRecurse) {
    2931      662713 :   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
    2932             :   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
    2933             : 
    2934      713513 :   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
    2935       95735 :     if (Constant *CRHS = dyn_cast<Constant>(RHS))
    2936       44935 :       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
    2937             : 
    2938             :     // If we have a constant, make sure it is on the RHS.
    2939        5865 :     std::swap(LHS, RHS);
    2940        5865 :     Pred = CmpInst::getSwappedPredicate(Pred);
    2941             :   }
    2942             : 
    2943     1235556 :   Type *ITy = GetCompareTy(LHS); // The return type.
    2944             : 
    2945             :   // icmp X, X -> true/false
    2946             :   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
    2947             :   // because X could be 0.
    2948     1234750 :   if (LHS == RHS || isa<UndefValue>(RHS))
    2949         837 :     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
    2950             : 
    2951      616941 :   if (Value *V = simplifyICmpOfBools(Pred, LHS, RHS, Q))
    2952             :     return V;
    2953             : 
    2954      613321 :   if (Value *V = simplifyICmpWithZero(Pred, LHS, RHS, Q))
    2955             :     return V;
    2956             : 
    2957      610632 :   if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS))
    2958             :     return V;
    2959             : 
    2960             :   // If both operands have range metadata, use the metadata
    2961             :   // to simplify the comparison.
    2962     1343984 :   if (isa<Instruction>(RHS) && isa<Instruction>(LHS)) {
    2963      234540 :     auto RHS_Instr = cast<Instruction>(RHS);
    2964      234540 :     auto LHS_Instr = cast<Instruction>(LHS);
    2965             : 
    2966       96895 :     if (RHS_Instr->getMetadata(LLVMContext::MD_range) &&
    2967         604 :         LHS_Instr->getMetadata(LLVMContext::MD_range)) {
    2968             :       auto RHS_CR = getConstantRangeFromMetadata(
    2969        1206 :           *RHS_Instr->getMetadata(LLVMContext::MD_range));
    2970             :       auto LHS_CR = getConstantRangeFromMetadata(
    2971        1206 :           *LHS_Instr->getMetadata(LLVMContext::MD_range));
    2972             : 
    2973        1206 :       auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR);
    2974         604 :       if (Satisfied_CR.contains(LHS_CR))
    2975           3 :         return ConstantInt::getTrue(RHS->getContext());
    2976             : 
    2977             :       auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion(
    2978        1205 :                 CmpInst::getInversePredicate(Pred), RHS_CR);
    2979         603 :       if (InversedSatisfied_CR.contains(LHS_CR))
    2980           1 :         return ConstantInt::getFalse(RHS->getContext());
    2981             :     }
    2982             :   }
    2983             : 
    2984             :   // Compare of cast, for example (zext X) != 0 -> X != 0
    2985      635594 :   if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
    2986       33958 :     Instruction *LI = cast<CastInst>(LHS);
    2987       33958 :     Value *SrcOp = LI->getOperand(0);
    2988       16979 :     Type *SrcTy = SrcOp->getType();
    2989       16979 :     Type *DstTy = LI->getType();
    2990             : 
    2991             :     // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
    2992             :     // if the integer type is the same size as the pointer type.
    2993       34355 :     if (MaxRecurse && isa<PtrToIntInst>(LI) &&
    2994         456 :         Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) {
    2995         593 :       if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
    2996             :         // Transfer the cast to the constant.
    2997         392 :         if (Value *V = SimplifyICmpInst(Pred, SrcOp,
    2998         196 :                                         ConstantExpr::getIntToPtr(RHSC, SrcTy),
    2999         196 :                                         Q, MaxRecurse-1))
    3000             :           return V;
    3001         402 :       } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
    3002         402 :         if (RI->getOperand(0)->getType() == SrcTy)
    3003             :           // Compare without the cast.
    3004         477 :           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
    3005         159 :                                           Q, MaxRecurse-1))
    3006             :             return V;
    3007             :       }
    3008             :     }
    3009             : 
    3010       16939 :     if (isa<ZExtInst>(LHS)) {
    3011             :       // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
    3012             :       // same type.
    3013       10124 :       if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
    3014        1376 :         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
    3015             :           // Compare X and Y.  Note that signed predicates become unsigned.
    3016        2064 :           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
    3017             :                                           SrcOp, RI->getOperand(0), Q,
    3018         688 :                                           MaxRecurse-1))
    3019             :             return V;
    3020             :       }
    3021             :       // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
    3022             :       // too.  If not, then try to deduce the result of the comparison.
    3023       17459 :       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
    3024             :         // Compute the constant that would happen if we truncated to SrcTy then
    3025             :         // reextended to DstTy.
    3026        8711 :         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
    3027        8711 :         Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
    3028             : 
    3029             :         // If the re-extended constant didn't change then this is effectively
    3030             :         // also a case of comparing two zero-extended values.
    3031        8711 :         if (RExt == CI && MaxRecurse)
    3032       17262 :           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
    3033        8631 :                                         SrcOp, Trunc, Q, MaxRecurse-1))
    3034             :             return V;
    3035             : 
    3036             :         // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
    3037             :         // there.  Use this to work out the result of the comparison.
    3038        5176 :         if (RExt != CI) {
    3039          80 :           switch (Pred) {
    3040           0 :           default: llvm_unreachable("Unknown ICmp predicate!");
    3041             :           // LHS <u RHS.
    3042          57 :           case ICmpInst::ICMP_EQ:
    3043             :           case ICmpInst::ICMP_UGT:
    3044             :           case ICmpInst::ICMP_UGE:
    3045          57 :             return ConstantInt::getFalse(CI->getContext());
    3046             : 
    3047          14 :           case ICmpInst::ICMP_NE:
    3048             :           case ICmpInst::ICMP_ULT:
    3049             :           case ICmpInst::ICMP_ULE:
    3050          14 :             return ConstantInt::getTrue(CI->getContext());
    3051             : 
    3052             :           // LHS is non-negative.  If RHS is negative then LHS >s LHS.  If RHS
    3053             :           // is non-negative then LHS <s RHS.
    3054           4 :           case ICmpInst::ICMP_SGT:
    3055             :           case ICmpInst::ICMP_SGE:
    3056           4 :             return CI->getValue().isNegative() ?
    3057           2 :               ConstantInt::getTrue(CI->getContext()) :
    3058           6 :               ConstantInt::getFalse(CI->getContext());
    3059             : 
    3060           5 :           case ICmpInst::ICMP_SLT:
    3061             :           case ICmpInst::ICMP_SLE:
    3062           5 :             return CI->getValue().isNegative() ?
    3063           3 :               ConstantInt::getFalse(CI->getContext()) :
    3064           8 :               ConstantInt::getTrue(CI->getContext());
    3065             :           }
    3066             :         }
    3067             :       }
    3068             :     }
    3069             : 
    3070       13323 :     if (isa<SExtInst>(LHS)) {
    3071             :       // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
    3072             :       // same type.
    3073        1140 :       if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
    3074         312 :         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
    3075             :           // Compare X and Y.  Note that the predicate does not change.
    3076         459 :           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
    3077         153 :                                           Q, MaxRecurse-1))
    3078             :             return V;
    3079             :       }
    3080             :       // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
    3081             :       // too.  If not, then try to deduce the result of the comparison.
    3082        1625 :       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
    3083             :         // Compute the constant that would happen if we truncated to SrcTy then
    3084             :         // reextended to DstTy.
    3085         797 :         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
    3086         797 :         Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
    3087             : 
    3088             :         // If the re-extended constant didn't change then this is effectively
    3089             :         // also a case of comparing two sign-extended values.
    3090         797 :         if (RExt == CI && MaxRecurse)
    3091         776 :           if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1))
    3092             :             return V;
    3093             : 
    3094             :         // Otherwise the upper bits of LHS are all equal, while RHS has varying
    3095             :         // bits there.  Use this to work out the result of the comparison.
    3096         728 :         if (RExt != CI) {
    3097          21 :           switch (Pred) {
    3098           0 :           default: llvm_unreachable("Unknown ICmp predicate!");
    3099           5 :           case ICmpInst::ICMP_EQ:
    3100           5 :             return ConstantInt::getFalse(CI->getContext());
    3101           8 :           case ICmpInst::ICMP_NE:
    3102           8 :             return ConstantInt::getTrue(CI->getContext());
    3103             : 
    3104             :           // If RHS is non-negative then LHS <s RHS.  If RHS is negative then
    3105             :           // LHS >s RHS.
    3106           2 :           case ICmpInst::ICMP_SGT:
    3107             :           case ICmpInst::ICMP_SGE:
    3108           2 :             return CI->getValue().isNegative() ?
    3109           1 :               ConstantInt::getTrue(CI->getContext()) :
    3110           3 :               ConstantInt::getFalse(CI->getContext());
    3111           2 :           case ICmpInst::ICMP_SLT:
    3112             :           case ICmpInst::ICMP_SLE:
    3113           2 :             return CI->getValue().isNegative() ?
    3114           1 :               ConstantInt::getFalse(CI->getContext()) :
    3115           3 :               ConstantInt::getTrue(CI->getContext());
    3116             : 
    3117             :           // If LHS is non-negative then LHS <u RHS.  If LHS is negative then
    3118             :           // LHS >u RHS.
    3119           3 :           case ICmpInst::ICMP_UGT:
    3120             :           case ICmpInst::ICMP_UGE:
    3121             :             // Comparison is true iff the LHS <s 0.
    3122           3 :             if (MaxRecurse)
    3123           6 :               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
    3124           3 :                                               Constant::getNullValue(SrcTy),
    3125           3 :                                               Q, MaxRecurse-1))
    3126             :                 return V;
    3127             :             break;
    3128           1 :           case ICmpInst::ICMP_ULT:
    3129             :           case ICmpInst::ICMP_ULE:
    3130             :             // Comparison is true iff the LHS >=s 0.
    3131           1 :             if (MaxRecurse)
    3132           2 :               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
    3133           1 :                                               Constant::getNullValue(SrcTy),
    3134           1 :                                               Q, MaxRecurse-1))
    3135             :                 return V;
    3136             :             break;
    3137             :           }
    3138             :         }
    3139             :       }
    3140             :     }
    3141             :   }
    3142             : 
    3143             :   // icmp eq|ne X, Y -> false|true if X != Y
    3144     1049687 :   if (ICmpInst::isEquality(Pred) &&
    3145      443497 :       isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) {
    3146         772 :     return Pred == ICmpInst::ICMP_NE ? getTrue(ITy) : getFalse(ITy);
    3147             :   }
    3148             : 
    3149      605804 :   if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
    3150             :     return V;
    3151             : 
    3152      605704 :   if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
    3153             :     return V;
    3154             : 
    3155             :   // Simplify comparisons of related pointers using a powerful, recursive
    3156             :   // GEP-walk when we have target data available..
    3157     1210812 :   if (LHS->getType()->isPointerTy())
    3158      415032 :     if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI, LHS,
    3159      207516 :                                      RHS))
    3160             :       return C;
    3161      605077 :   if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
    3162         939 :     if (auto *CRHS = dyn_cast<PtrToIntOperator>(RHS))
    3163         504 :       if (Q.DL.getTypeSizeInBits(CLHS->getPointerOperandType()) ==
    3164         459 :               Q.DL.getTypeSizeInBits(CLHS->getType()) &&
    3165         414 :           Q.DL.getTypeSizeInBits(CRHS->getPointerOperandType()) ==
    3166         207 :               Q.DL.getTypeSizeInBits(CRHS->getType()))
    3167         621 :         if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI,
    3168             :                                          CLHS->getPointerOperand(),
    3169         207 :                                          CRHS->getPointerOperand()))
    3170             :           return C;
    3171             : 
    3172      610593 :   if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
    3173        6818 :     if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
    3174        1276 :       if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
    3175         633 :           GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
    3176          12 :           (ICmpInst::isEquality(Pred) ||
    3177          10 :            (GLHS->isInBounds() && GRHS->isInBounds() &&
    3178           2 :             Pred == ICmpInst::getSignedPredicate(Pred)))) {
    3179             :         // The bases are equal and the indices are constant.  Build a constant
    3180             :         // expression GEP with the same indices and a null base pointer to see
    3181             :         // what constant folding can make out of it.
    3182           2 :         Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
    3183           8 :         SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
    3184           8 :         Constant *NewLHS = ConstantExpr::getGetElementPtr(
    3185           2 :             GLHS->getSourceElementType(), Null, IndicesLHS);
    3186             : 
    3187           8 :         SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
    3188           8 :         Constant *NewRHS = ConstantExpr::getGetElementPtr(
    3189           2 :             GLHS->getSourceElementType(), Null, IndicesRHS);
    3190           2 :         return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
    3191             :       }
    3192             :     }
    3193             :   }
    3194             : 
    3195             :   // If the comparison is with the result of a select instruction, check whether
    3196             :   // comparing with either branch of the select always yields the same value.
    3197     1202673 :   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
    3198        7516 :     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
    3199             :       return V;
    3200             : 
    3201             :   // If the comparison is with the result of a phi instruction, check whether
    3202             :   // doing the compare with each incoming phi value yields a common result.
    3203     1153888 :   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
    3204       60751 :     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
    3205             :       return V;
    3206             : 
    3207             :   return nullptr;
    3208             : }
    3209             : 
    3210      553422 : Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
    3211             :                               const SimplifyQuery &Q) {
    3212      553422 :   return ::SimplifyICmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
    3213             : }
    3214             : 
    3215             : /// Given operands for an FCmpInst, see if we can fold the result.
    3216             : /// If not, this returns null.
    3217        7448 : static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
    3218             :                                FastMathFlags FMF, const SimplifyQuery &Q,
    3219             :                                unsigned MaxRecurse) {
    3220        7448 :   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
    3221             :   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
    3222             : 
    3223        7839 :   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
    3224         528 :     if (Constant *CRHS = dyn_cast<Constant>(RHS))
    3225         137 :       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
    3226             : 
    3227             :     // If we have a constant, make sure it is on the RHS.
    3228         254 :     std::swap(LHS, RHS);
    3229         254 :     Pred = CmpInst::getSwappedPredicate(Pred);
    3230             :   }
    3231             : 
    3232             :   // Fold trivial predicates.
    3233       14622 :   Type *RetTy = GetCompareTy(LHS);
    3234        7311 :   if (Pred == FCmpInst::FCMP_FALSE)
    3235          35 :     return getFalse(RetTy);
    3236        7276 :   if (Pred == FCmpInst::FCMP_TRUE)
    3237          35 :     return getTrue(RetTy);
    3238             : 
    3239             :   // UNO/ORD predicates can be trivially folded if NaNs are ignored.
    3240        7241 :   if (FMF.noNaNs()) {
    3241         209 :     if (Pred == FCmpInst::FCMP_UNO)
    3242           1 :       return getFalse(RetTy);
    3243         208 :     if (Pred == FCmpInst::FCMP_ORD)
    3244           1 :       return getTrue(RetTy);
    3245             :   }
    3246             : 
    3247             :   // fcmp pred x, undef  and  fcmp pred undef, x
    3248             :   // fold to true if unordered, false if ordered
    3249       21717 :   if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) {
    3250             :     // Choosing NaN for the undef will always make unordered comparison succeed
    3251             :     // and ordered comparison fail.
    3252          28 :     return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
    3253             :   }
    3254             : 
    3255             :   // fcmp x,x -> true/false.  Not all compares are foldable.
    3256        7211 :   if (LHS == RHS) {
    3257         140 :     if (CmpInst::isTrueWhenEqual(Pred))
    3258           2 :       return getTrue(RetTy);
    3259         138 :     if (CmpInst::isFalseWhenEqual(Pred))
    3260           7 :       return getFalse(RetTy);
    3261             :   }
    3262             : 
    3263             :   // Handle fcmp with constant RHS
    3264        7202 :   const ConstantFP *CFP = nullptr;
    3265       10298 :   if (const auto *RHSC = dyn_cast<Constant>(RHS)) {
    3266        6192 :     if (RHS->getType()->isVectorTy())
    3267         128 :       CFP = dyn_cast_or_null<ConstantFP>(RHSC->getSplatValue());
    3268             :     else
    3269             :       CFP = dyn_cast<ConstantFP>(RHSC);
    3270             :   }
    3271        3077 :   if (CFP) {
    3272             :     // If the constant is a nan, see if we can fold the comparison based on it.
    3273        6154 :     if (CFP->getValueAPF().isNaN()) {
    3274          13 :       if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
    3275           7 :         return getFalse(RetTy);
    3276             :       assert(FCmpInst::isUnordered(Pred) &&
    3277             :              "Comparison must be either ordered or unordered!");
    3278             :       // True if unordered.
    3279           6 :       return getTrue(RetTy);
    3280             :     }
    3281             :     // Check whether the constant is an infinity.
    3282        6128 :     if (CFP->getValueAPF().isInfinity()) {
    3283         354 :       if (CFP->getValueAPF().isNegative()) {
    3284          74 :         switch (Pred) {
    3285           1 :         case FCmpInst::FCMP_OLT:
    3286             :           // No value is ordered and less than negative infinity.
    3287           1 :           return getFalse(RetTy);
    3288           1 :         case FCmpInst::FCMP_UGE:
    3289             :           // All values are unordered with or at least negative infinity.
    3290           1 :           return getTrue(RetTy);
    3291             :         default:
    3292             :           break;
    3293             :         }
    3294             :       } else {
    3295         103 :         switch (Pred) {
    3296           1 :         case FCmpInst::FCMP_OGT:
    3297             :           // No value is ordered and greater than infinity.
    3298           1 :           return getFalse(RetTy);
    3299           3 :         case FCmpInst::FCMP_ULE:
    3300             :           // All values are unordered with and at most infinity.
    3301           3 :           return getTrue(RetTy);
    3302             :         default:
    3303             :           break;
    3304             :         }
    3305             :       }
    3306             :     }
    3307        6116 :     if (CFP->getValueAPF().isZero()) {
    3308        1684 :       switch (Pred) {
    3309          24 :       case FCmpInst::FCMP_UGE:
    3310          24 :         if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
    3311           6 :           return getTrue(RetTy);
    3312             :         break;
    3313         142 :       case FCmpInst::FCMP_OLT:
    3314             :         // X < 0
    3315         142 :         if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
    3316           7 :           return getFalse(RetTy);
    3317             :         break;
    3318             :       default:
    3319             :         break;
    3320             :       }
    3321             :     }
    3322             :   }
    3323             : 
    3324             :   // If the comparison is with the result of a select instruction, check whether
    3325             :   // comparing with either branch of the select always yields the same value.
    3326       14164 :   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
    3327         218 :     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
    3328             :       return V;
    3329             : 
    3330             :   // If the comparison is with the result of a phi instruction, check whether
    3331             :   // doing the compare with each incoming phi value yields a common result.
    3332       14258 :   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
    3333         136 :     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
    3334             :       return V;
    3335             : 
    3336             :   return nullptr;
    3337             : }
    3338             : 
    3339        7061 : Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
    3340             :                               FastMathFlags FMF, const SimplifyQuery &Q) {
    3341        7061 :   return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit);
    3342             : }
    3343             : 
    3344             : /// See if V simplifies when its operand Op is replaced with RepOp.
    3345     1145734 : static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
    3346             :                                            const SimplifyQuery &Q,
    3347             :                                            unsigned MaxRecurse) {
    3348             :   // Trivial replacement.
    3349     1145734 :   if (V == Op)
    3350             :     return RepOp;
    3351             : 
    3352             :   // We cannot replace a constant, and shouldn't even try.
    3353     1141706 :   if (isa<Constant>(Op))
    3354             :     return nullptr;
    3355             : 
    3356        4886 :   auto *I = dyn_cast<Instruction>(V);
    3357             :   if (!I)
    3358             :     return nullptr;
    3359             : 
    3360             :   // If this is a binary operator, try to simplify it with the replaced op.
    3361         730 :   if (auto *B = dyn_cast<BinaryOperator>(I)) {
    3362             :     // Consider:
    3363             :     //   %cmp = icmp eq i32 %x, 2147483647
    3364             :     //   %add = add nsw i32 %x, 1
    3365             :     //   %sel = select i1 %cmp, i32 -2147483648, i32 %add
    3366             :     //
    3367             :     // We can't replace %sel with %add unless we strip away the flags.
    3368         730 :     if (isa<OverflowingBinaryOperator>(B))
    3369         204 :       if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap())
    3370             :         return nullptr;
    3371         622 :     if (isa<PossiblyExactOperator>(B))
    3372         132 :       if (B->isExact())
    3373             :         return nullptr;
    3374             : 
    3375         521 :     if (MaxRecurse) {
    3376        1042 :       if (B->getOperand(0) == Op)
    3377         153 :         return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q,
    3378          51 :                              MaxRecurse - 1);
    3379         940 :       if (B->getOperand(1) == Op)
    3380           6 :         return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q,
    3381           2 :                              MaxRecurse - 1);
    3382             :     }
    3383             :   }
    3384             : 
    3385             :   // Same for CmpInsts.
    3386          35 :   if (CmpInst *C = dyn_cast<CmpInst>(I)) {
    3387          35 :     if (MaxRecurse) {
    3388          35 :       if (C->getOperand(0) == Op)
    3389           3 :         return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q,
    3390           1 :                                MaxRecurse - 1);
    3391          34 :       if (C->getOperand(1) == Op)
    3392           0 :         return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q,
    3393           0 :                                MaxRecurse - 1);
    3394             :     }
    3395             :   }
    3396             : 
    3397             :   // TODO: We could hand off more cases to instsimplify here.
    3398             : 
    3399             :   // If all operands are constant after substituting Op for RepOp then we can
    3400             :   // constant fold the instruction.
    3401        4623 :   if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
    3402             :     // Build a list of all constant operands.
    3403        6737 :     SmallVector<Constant *, 8> ConstOps;
    3404        8557 :     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
    3405        8832 :       if (I->getOperand(i) == Op)
    3406         298 :         ConstOps.push_back(CRepOp);
    3407       12354 :       else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i)))
    3408        1007 :         ConstOps.push_back(COp);
    3409             :       else
    3410             :         break;
    3411             :     }
    3412             : 
    3413             :     // All operands were constants, fold it.
    3414        7252 :     if (ConstOps.size() == I->getNumOperands()) {
    3415         515 :       if (CmpInst *C = dyn_cast<CmpInst>(I))
    3416           0 :         return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
    3417         515 :                                                ConstOps[1], Q.DL, Q.TLI);
    3418             : 
    3419         186 :       if (LoadInst *LI = dyn_cast<LoadInst>(I))
    3420         186 :         if (!LI->isVolatile())
    3421         348 :           return ConstantFoldLoadFromConstPtr(ConstOps[0], LI->getType(), Q.DL);
    3422             : 
    3423         682 :       return ConstantFoldInstOperands(I, ConstOps, Q.DL, Q.TLI);
    3424             :     }
    3425             :   }
    3426             : 
    3427        4108 :   return nullptr;
    3428             : }
    3429             : 
    3430             : /// Try to simplify a select instruction when its condition operand is an
    3431             : /// integer comparison where one operand of the compare is a constant.
    3432       17149 : static Value *simplifySelectBitTest(Value *TrueVal, Value *FalseVal, Value *X,
    3433             :                                     const APInt *Y, bool TrueWhenUnset) {
    3434             :   const APInt *C;
    3435             : 
    3436             :   // (X & Y) == 0 ? X & ~Y : X  --> X
    3437             :   // (X & Y) != 0 ? X & ~Y : X  --> X & ~Y
    3438       35256 :   if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) &&
    3439       51491 :       *Y == ~*C)
    3440          11 :     return TrueWhenUnset ? FalseVal : TrueVal;
    3441             : 
    3442             :   // (X & Y) == 0 ? X : X & ~Y  --> X & ~Y
    3443             :   // (X & Y) != 0 ? X : X & ~Y  --> X
    3444       37370 :   if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) &&
    3445       51458 :       *Y == ~*C)
    3446          11 :     return TrueWhenUnset ? FalseVal : TrueVal;
    3447             : 
    3448       17127 :   if (Y->isPowerOf2()) {
    3449             :     // (X & Y) == 0 ? X | Y : X  --> X | Y
    3450             :     // (X & Y) != 0 ? X | Y : X  --> X
    3451        4160 :     if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) &&
    3452          16 :         *Y == *C)
    3453           8 :       return TrueWhenUnset ? TrueVal : FalseVal;
    3454             : 
    3455             :     // (X & Y) == 0 ? X : X | Y  --> X
    3456             :     // (X & Y) != 0 ? X : X | Y  --> X | Y
    3457        2663 :     if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
    3458          14 :         *Y == *C)
    3459           7 :       return TrueWhenUnset ? TrueVal : FalseVal;
    3460             :   }
    3461             : 
    3462             :   return nullptr;
    3463             : }
    3464             : 
    3465             : /// An alternative way to test if a bit is set or not uses sgt/slt instead of
    3466             : /// eq/ne.
    3467      371328 : static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *CmpRHS,
    3468             :                                            ICmpInst::Predicate Pred,
    3469             :                                            Value *TrueVal, Value *FalseVal) {
    3470             :   Value *X;
    3471      742656 :   APInt Mask;
    3472      371328 :   if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask))
    3473             :     return nullptr;
    3474             : 
    3475       15276 :   return simplifySelectBitTest(TrueVal, FalseVal, X, &Mask,
    3476       15276 :                                Pred == ICmpInst::ICMP_EQ);
    3477             : }
    3478             : 
    3479             : /// Try to simplify a select instruction when its condition operand is an
    3480             : /// integer comparison.
    3481      456647 : static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
    3482             :                                          Value *FalseVal, const SimplifyQuery &Q,
    3483             :                                          unsigned MaxRecurse) {
    3484             :   ICmpInst::Predicate Pred;
    3485             :   Value *CmpLHS, *CmpRHS;
    3486     1741281 :   if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
    3487             :     return nullptr;
    3488             : 
    3489      981485 :   if (ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero())) {
    3490             :     Value *X;
    3491             :     const APInt *Y;
    3492      868372 :     if (match(CmpLHS, m_And(m_Value(X), m_APInt(Y))))
    3493        3746 :       if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, Y,
    3494        1873 :                                            Pred == ICmpInst::ICMP_EQ))
    3495          12 :         return V;
    3496             :   }
    3497             : 
    3498             :   // Check for other compares that behave like bit test.
    3499      742656 :   if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, CmpRHS, Pred,
    3500      371328 :                                               TrueVal, FalseVal))
    3501             :     return V;
    3502             : 
    3503      371303 :   if (CondVal->hasOneUse()) {
    3504             :     const APInt *C;
    3505       66286 :     if (match(CmpRHS, m_APInt(C))) {
    3506             :       // X < MIN ? T : F  -->  F
    3507       12254 :       if (Pred == ICmpInst::ICMP_SLT && C->isMinSignedValue())
    3508           0 :         return FalseVal;
    3509             :       // X < MIN ? T : F  -->  F
    3510       15847 :       if (Pred == ICmpInst::ICMP_ULT && C->isMinValue())
    3511             :         return FalseVal;
    3512             :       // X > MAX ? T : F  -->  F
    3513       12254 :       if (Pred == ICmpInst::ICMP_SGT && C->isMaxSignedValue())
    3514             :         return FalseVal;
    3515             :       // X > MAX ? T : F  -->  F
    3516       13390 :       if (Pred == ICmpInst::ICMP_UGT && C->isMaxValue())
    3517             :         return FalseVal;
    3518             :     }
    3519             :   }
    3520             : 
    3521             :   // If we have an equality comparison, then we know the value in one of the
    3522             :   // arms of the select. See if substituting this value into the arm and
    3523             :   // simplifying the result yields the same value as the other arm.
    3524      371303 :   if (Pred == ICmpInst::ICMP_EQ) {
    3525      119120 :     if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
    3526      238227 :             TrueVal ||
    3527      119107 :         SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
    3528             :             TrueVal)
    3529             :       return FalseVal;
    3530      119105 :     if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
    3531      238208 :             FalseVal ||
    3532      119103 :         SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
    3533             :             FalseVal)
    3534             :       return FalseVal;
    3535      252183 :   } else if (Pred == ICmpInst::ICMP_NE) {
    3536      167329 :     if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
    3537      334653 :             FalseVal ||
    3538      167324 :         SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
    3539             :             FalseVal)
    3540             :       return TrueVal;
    3541      167323 :     if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
    3542      334646 :             TrueVal ||
    3543      167323 :         SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
    3544             :             TrueVal)
    3545             :       return TrueVal;
    3546             :   }
    3547             : 
    3548             :   return nullptr;
    3549             : }
    3550             : 
    3551             : /// Given operands for a SelectInst, see if we can fold the result.
    3552             : /// If not, this returns null.
    3553      460757 : static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal,
    3554             :                                  Value *FalseVal, const SimplifyQuery &Q,
    3555             :                                  unsigned MaxRecurse) {
    3556             :   // select true, X, Y  -> X
    3557             :   // select false, X, Y -> Y
    3558      464779 :   if (Constant *CB = dyn_cast<Constant>(CondVal)) {
    3559        4022 :     if (CB->isAllOnesValue())
    3560             :       return TrueVal;
    3561        1745 :     if (CB->isNullValue())
    3562             :       return FalseVal;
    3563             :   }
    3564             : 
    3565             :   // select C, X, X -> X
    3566      456836 :   if (TrueVal == FalseVal)
    3567             :     return TrueVal;
    3568             : 
    3569      913410 :   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
    3570          43 :     if (isa<Constant>(FalseVal))
    3571             :       return FalseVal;
    3572             :     return TrueVal;
    3573             :   }
    3574      913324 :   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
    3575             :     return FalseVal;
    3576      913304 :   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
    3577             :     return TrueVal;
    3578             : 
    3579      456647 :   if (Value *V =
    3580      456647 :           simplifySelectWithICmpCond(CondVal, TrueVal, FalseVal, Q, MaxRecurse))
    3581             :     return V;
    3582             : 
    3583      456587 :   return nullptr;
    3584             : }
    3585             : 
    3586      460757 : Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
    3587             :                                 const SimplifyQuery &Q) {
    3588      460757 :   return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Q, RecursionLimit);
    3589             : }
    3590             : 
    3591             : /// Given operands for an GetElementPtrInst, see if we can fold the result.
    3592             : /// If not, this returns null.
    3593     1517151 : static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
    3594             :                               const SimplifyQuery &Q, unsigned) {
    3595             :   // The type of the GEP pointer operand.
    3596             :   unsigned AS =
    3597     6068604 :       cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace();
    3598             : 
    3599             :   // getelementptr P -> P.
    3600     1517151 :   if (Ops.size() == 1)
    3601             :     return Ops[0];
    3602             : 
    3603             :   // Compute the (pointer) type returned by the GEP instruction.
    3604     1517094 :   Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1));
    3605     1517094 :   Type *GEPTy = PointerType::get(LastType, AS);
    3606     1519174 :   if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
    3607        2080 :     GEPTy = VectorType::get(GEPTy, VT->getNumElements());
    3608     1515858 :   else if (VectorType *VT = dyn_cast<VectorType>(Ops[1]->getType()))
    3609         844 :     GEPTy = VectorType::get(GEPTy, VT->getNumElements());
    3610             : 
    3611     3034188 :   if (isa<UndefValue>(Ops[0]))
    3612        2019 :     return UndefValue::get(GEPTy);
    3613             : 
    3614     1515075 :   if (Ops.size() == 2) {
    3615             :     // getelementptr P, 0 -> P.
    3616      343771 :     if (match(Ops[1], m_Zero()))
    3617        4115 :       return Ops[0];
    3618             : 
    3619      206937 :     Type *Ty = SrcTy;
    3620      206937 :     if (Ty->isSized()) {
    3621             :       Value *P;
    3622             :       uint64_t C;
    3623      206937 :       uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty);
    3624             :       // getelementptr P, N -> P if P points to a type of zero size.
    3625      206937 :       if (TyAllocSize == 0)
    3626          14 :         return Ops[0];
    3627             : 
    3628             :       // The following transforms are only safe if the ptrtoint cast
    3629             :       // doesn't truncate the pointers.
    3630      413870 :       if (Ops[1]->getType()->getScalarSizeInBits() ==
    3631      413870 :           Q.DL.getPointerSizeInBits(AS)) {
    3632          24 :         auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * {
    3633          15 :           if (match(P, m_Zero()))
    3634           3 :             return Constant::getNullValue(GEPTy);
    3635             :           Value *Temp;
    3636          27 :           if (match(P, m_PtrToInt(m_Value(Temp))))
    3637          18 :             if (Temp->getType() == GEPTy)
    3638             :               return Temp;
    3639             :           return nullptr;
    3640      195112 :         };
    3641             : 
    3642             :         // getelementptr V, (sub P, V) -> P if P points to a type of size 1.
    3643      280509 :         if (TyAllocSize == 1 &&
    3644      707491 :             match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0])))))
    3645           3 :           if (Value *R = PtrToIntOrZero(P))
    3646          10 :             return R;
    3647             : 
    3648             :         // getelementptr V, (ashr (sub P, V), C) -> Q
    3649             :         // if P points to a type of size 1 << C.
    3650      390220 :         if (match(Ops[1],
    3651     1365765 :                   m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
    3652      390225 :                          m_ConstantInt(C))) &&
    3653           5 :             TyAllocSize == 1ULL << C)
    3654           5 :           if (Value *R = PtrToIntOrZero(P))
    3655             :             return R;
    3656             : 
    3657             :         // getelementptr V, (sdiv (sub P, V), C) -> Q
    3658             :         // if P points to a type of size C.
    3659      585315 :         if (match(Ops[1],
    3660     1365735 :                   m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
    3661      195105 :                          m_SpecificInt(TyAllocSize))))
    3662           4 :           if (Value *R = PtrToIntOrZero(P))
    3663             :             return R;
    3664             :       }
    3665             :     }
    3666             :   }
    3667             : 
    3668     1738265 :   if (Q.DL.getTypeAllocSize(LastType) == 1 &&
    3669      681951 :       all_of(Ops.slice(1).drop_back(1),
    3670      440371 :              [](Value *Idx) { return match(Idx, m_Zero()); })) {
    3671             :     unsigned PtrWidth =
    3672      642300 :         Q.DL.getPointerSizeInBits(Ops[0]->getType()->getPointerAddressSpace());
    3673      428200 :     if (Q.DL.getTypeSizeInBits(Ops.back()->getType()) == PtrWidth) {
    3674      296138 :       APInt BasePtrOffset(PtrWidth, 0);
    3675             :       Value *StrippedBasePtr =
    3676      148071 :           Ops[0]->stripAndAccumulateInBoundsConstantOffsets(Q.DL,
    3677      148071 :                                                             BasePtrOffset);
    3678             : 
    3679             :       // gep (gep V, C), (sub 0, V) -> C
    3680      444213 :       if (match(Ops.back(),
    3681      592284 :                 m_Sub(m_Zero(), m_PtrToInt(m_Specific(StrippedBasePtr))))) {
    3682           3 :         auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset);
    3683           7 :         return ConstantExpr::getIntToPtr(CI, GEPTy);
    3684             :       }
    3685             :       // gep (gep V, C), (xor V, -1) -> C-1
    3686      444204 :       if (match(Ops.back(),
    3687      740340 :                 m_Xor(m_PtrToInt(m_Specific(StrippedBasePtr)), m_AllOnes()))) {
    3688           4 :         auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset - 1);
    3689           1 :         return ConstantExpr::getIntToPtr(CI, GEPTy);
    3690             :       }
    3691             :     }
    3692             :   }
    3693             : 
    3694             :   // Check to see if this is constant foldable.
    3695     5500811 :   if (!all_of(Ops, [](Value *V) { return isa<Constant>(V); }))
    3696             :     return nullptr;
    3697             : 
    3698       21572 :   auto *CE = ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]),
    3699        5393 :                                             Ops.slice(1));
    3700        5393 :   if (auto *CEFolded = ConstantFoldConstant(CE, Q.DL))
    3701             :     return CEFolded;
    3702             :   return CE;
    3703             : }
    3704             : 
    3705     1517151 : Value *llvm::SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
    3706             :                              const SimplifyQuery &Q) {
    3707     1517151 :   return ::SimplifyGEPInst(SrcTy, Ops, Q, RecursionLimit);
    3708             : }
    3709             : 
    3710             : /// Given operands for an InsertValueInst, see if we can fold the result.
    3711             : /// If not, this returns null.
    3712       19199 : static Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
    3713             :                                       ArrayRef<unsigned> Idxs, const SimplifyQuery &Q,
    3714             :                                       unsigned) {
    3715        9607 :   if (Constant *CAgg = dyn_cast<Constant>(Agg))
    3716         138 :     if (Constant *CVal = dyn_cast<Constant>(Val))
    3717         138 :       return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
    3718             : 
    3719             :   // insertvalue x, undef, n -> x
    3720       38122 :   if (match(Val, m_Undef()))
    3721             :     return Agg;
    3722             : 
    3723             :   // insertvalue x, (extractvalue y, n), n
    3724        3047 :   if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
    3725        6066 :     if (EV->getAggregateOperand()->getType() == Agg->getType() &&
    3726        3019 :         EV->getIndices() == Idxs) {
    3727             :       // insertvalue undef, (extractvalue y, n), n -> y
    3728        6038 :       if (match(Agg, m_Undef()))
    3729             :         return EV->getAggregateOperand();
    3730             : 
    3731             :       // insertvalue y, (extractvalue y, n), n -> y
    3732        1526 :       if (Agg == EV->getAggregateOperand())
    3733             :         return Agg;
    3734             :     }
    3735             : 
    3736             :   return nullptr;
    3737             : }
    3738             : 
    3739       19199 : Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
    3740             :                                      ArrayRef<unsigned> Idxs,
    3741             :                                      const SimplifyQuery &Q) {
    3742       19199 :   return ::SimplifyInsertValueInst(Agg, Val, Idxs, Q, RecursionLimit);
    3743             : }
    3744             : 
    3745             : /// Given operands for an ExtractValueInst, see if we can fold the result.
    3746             : /// If not, this returns null.
    3747      640123 : static Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
    3748             :                                        const SimplifyQuery &, unsigned) {
    3749          10 :   if (auto *CAgg = dyn_cast<Constant>(Agg))
    3750          10 :     return ConstantFoldExtractValueInstruction(CAgg, Idxs);
    3751             : 
    3752             :   // extractvalue x, (insertvalue y, elt, n), n -> elt
    3753      640113 :   unsigned NumIdxs = Idxs.size();
    3754      640441 :   for (auto *IVI = dyn_cast<InsertValueInst>(Agg); IVI != nullptr;
    3755         360 :        IVI = dyn_cast<InsertValueInst>(IVI->getAggregateOperand())) {
    3756         813 :     ArrayRef<unsigned> InsertValueIdxs = IVI->getIndices();
    3757         813 :     unsigned NumInsertValueIdxs = InsertValueIdxs.size();
    3758         813 :     unsigned NumCommonIdxs = std::min(NumInsertValueIdxs, NumIdxs);
    3759        3252 :     if (InsertValueIdxs.slice(0, NumCommonIdxs) ==
    3760             :         Idxs.slice(0, NumCommonIdxs)) {
    3761         453 :       if (NumIdxs == NumInsertValueIdxs)
    3762         447 :         return IVI->getInsertedValueOperand();
    3763           6 :       break;
    3764             :     }
    3765             :   }
    3766             : 
    3767             :   return nullptr;
    3768             : }
    3769             : 
    3770      640123 : Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
    3771             :                                       const SimplifyQuery &Q) {
    3772      640123 :   return ::SimplifyExtractValueInst(Agg, Idxs, Q, RecursionLimit);
    3773             : }
    3774             : 
    3775             : /// Given operands for an ExtractElementInst, see if we can fold the result.
    3776             : /// If not, this returns null.
    3777       18375 : static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &,
    3778             :                                          unsigned) {
    3779       18706 :   if (auto *CVec = dyn_cast<Constant>(Vec)) {
    3780          23 :     if (auto *CIdx = dyn_cast<Constant>(Idx))
    3781          23 :       return ConstantFoldExtractElementInstruction(CVec, CIdx);
    3782             : 
    3783             :     // The index is not relevant if our vector is a splat.
    3784         308 :     if (auto *Splat = CVec->getSplatValue())
    3785             :       return Splat;
    3786             : 
    3787         616 :     if (isa<UndefValue>(Vec))
    3788           2 :       return UndefValue::get(Vec->getType()->getVectorElementType());
    3789             :   }
    3790             : 
    3791             :   // If extracting a specified index from the vector, see if we can recursively
    3792             :   // find a previously computed scalar that was inserted into the vector.
    3793       17005 :   if (auto *IdxC = dyn_cast<ConstantInt>(Idx))
    3794       17005 :     if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue()))
    3795             :       return Elt;
    3796             : 
    3797             :   return nullptr;
    3798             : }
    3799             : 
    3800       18375 : Value *llvm::SimplifyExtractElementInst(Value *Vec, Value *Idx,
    3801             :                                         const SimplifyQuery &Q) {
    3802       18375 :   return ::SimplifyExtractElementInst(Vec, Idx, Q, RecursionLimit);
    3803             : }
    3804             : 
    3805             : /// See if we can fold the given phi. If not, returns null.
    3806     1757797 : static Value *SimplifyPHINode(PHINode *PN, const SimplifyQuery &Q) {
    3807             :   // If all of the PHI's incoming values are the same then replace the PHI node
    3808             :   // with the common value.
    3809     1757797 :   Value *CommonValue = nullptr;
    3810     1757797 :   bool HasUndefInput = false;
    3811     3538384 :   for (Value *Incoming : PN->incoming_values()) {
    3812             :     // If the incoming value is the phi node itself, it can safely be skipped.
    3813     3505948 :     if (Incoming == PN) continue;
    3814     7018415 :     if (isa<UndefValue>(Incoming)) {
    3815             :       // Remember that we saw an undef value, but otherwise ignore them.
    3816        7465 :       HasUndefInput = true;
    3817             :       continue;
    3818             :     }
    3819     3498010 :     if (CommonValue && Incoming != CommonValue)
    3820             :       return nullptr;  // Not the same, bail out.
    3821             :     CommonValue = Incoming;
    3822             :   }
    3823             : 
    3824             :   // If CommonValue is null then all of the incoming values were either undef or
    3825             :   // equal to the phi node itself.
    3826       32436 :   if (!CommonValue)
    3827          70 :     return UndefValue::get(PN->getType());
    3828             : 
    3829             :   // If we have a PHI node like phi(X, undef, X), where X is defined by some
    3830             :   // instruction, we cannot return X as the result of the PHI node unless it
    3831             :   // dominates the PHI block.
    3832       32366 :   if (HasUndefInput)
    3833        6995 :     return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr;
    3834             : 
    3835             :   return CommonValue;
    3836             : }
    3837             : 
    3838      623452 : static Value *SimplifyCastInst(unsigned CastOpc, Value *Op,
    3839             :                                Type *Ty, const SimplifyQuery &Q, unsigned MaxRecurse) {
    3840        5515 :   if (auto *C = dyn_cast<Constant>(Op))
    3841        5515 :     return ConstantFoldCastOperand(CastOpc, C, Ty, Q.DL);
    3842             : 
    3843       18568 :   if (auto *CI = dyn_cast<CastInst>(Op)) {
    3844       37136 :     auto *Src = CI->getOperand(0);
    3845       18568 :     Type *SrcTy = Src->getType();
    3846       18568 :     Type *MidTy = CI->getType();
    3847       18568 :     Type *DstTy = Ty;
    3848       18568 :     if (Src->getType() == Ty) {
    3849       11403 :       auto FirstOp = static_cast<Instruction::CastOps>(CI->getOpcode());
    3850       11403 :       auto SecondOp = static_cast<Instruction::CastOps>(CastOpc);
    3851             :       Type *SrcIntPtrTy =
    3852       11403 :           SrcTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(SrcTy) : nullptr;
    3853             :       Type *MidIntPtrTy =
    3854       11403 :           MidTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(MidTy) : nullptr;
    3855             :       Type *DstIntPtrTy =
    3856       11403 :           DstTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(DstTy) : nullptr;
    3857       11403 :       if (CastInst::isEliminableCastPair(FirstOp, SecondOp, SrcTy, MidTy, DstTy,
    3858             :                                          SrcIntPtrTy, MidIntPtrTy,
    3859             :                                          DstIntPtrTy) == Instruction::BitCast)
    3860             :         return Src;
    3861             :     }
    3862             :   }
    3863             : 
    3864             :   // bitcast x -> x
    3865      607202 :   if (CastOpc == Instruction::BitCast)
    3866      275009 :     if (Op->getType() == Ty)
    3867             :       return Op;
    3868             : 
    3869             :   return nullptr;
    3870             : }
    3871             : 
    3872      623451 : Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
    3873             :                               const SimplifyQuery &Q) {
    3874      623451 :   return ::SimplifyCastInst(CastOpc, Op, Ty, Q, RecursionLimit);
    3875             : }
    3876             : 
    3877             : /// For the given destination element of a shuffle, peek through shuffles to
    3878             : /// match a root vector source operand that contains that element in the same
    3879             : /// vector lane (ie, the same mask index), so we can eliminate the shuffle(s).
    3880       20354 : static Value *foldIdentityShuffles(int DestElt, Value *Op0, Value *Op1,
    3881             :                                    int MaskVal, Value *RootVec,
    3882             :                                    unsigned MaxRecurse) {
    3883       20888 :   if (!MaxRecurse--)
    3884             :     return nullptr;
    3885             : 
    3886             :   // Bail out if any mask value is undefined. That kind of shuffle may be
    3887             :   // simplified further based on demanded bits or other folds.
    3888       20886 :   if (MaskVal == -1)
    3889             :     return nullptr;
    3890             : 
    3891             :   // The mask value chooses which source operand we need to look at next.
    3892       41772 :   int InVecNumElts = Op0->getType()->getVectorNumElements();
    3893       20886 :   int RootElt = MaskVal;
    3894       20886 :   Value *SourceOp = Op0;
    3895       20886 :   if (MaskVal >= InVecNumElts) {
    3896        2221 :     RootElt = MaskVal - InVecNumElts;
    3897        2221 :     SourceOp = Op1;
    3898             :   }
    3899             : 
    3900             :   // If the source operand is a shuffle itself, look through it to find the
    3901             :   // matching root vector.
    3902         534 :   if (auto *SourceShuf = dyn_cast<ShuffleVectorInst>(SourceOp)) {
    3903        2136 :     return foldIdentityShuffles(
    3904             :         DestElt, SourceShuf->getOperand(0), SourceShuf->getOperand(1),
    3905         534 :         SourceShuf->getMaskValue(RootElt), RootVec, MaxRecurse);
    3906             :   }
    3907             : 
    3908             :   // TODO: Look through bitcasts? What if the bitcast changes the vector element
    3909             :   // size?
    3910             : 
    3911             :   // The source operand is not a shuffle. Initialize the root vector value for
    3912             :   // this shuffle if that has not been done yet.
    3913       20352 :   if (!RootVec)
    3914       12965 :     RootVec = SourceOp;
    3915             : 
    3916             :   // Give up as soon as a source operand does not match the existing root value.
    3917       20352 :   if (RootVec != SourceOp)
    3918             :     return nullptr;
    3919             : 
    3920             :   // The element must be coming from the same lane in the source vector
    3921             :   // (although it may have crossed lanes in intermediate shuffles).
    3922       18515 :   if (RootElt != DestElt)
    3923             :     return nullptr;
    3924             : 
    3925       11817 :   return RootVec;
    3926             : }
    3927             : 
    3928       17377 : static Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
    3929             :                                         Type *RetTy, const SimplifyQuery &Q,
    3930             :                                         unsigned MaxRecurse) {
    3931       34754 :   if (isa<UndefValue>(Mask))
    3932           9 :     return UndefValue::get(RetTy);
    3933             : 
    3934       17368 :   Type *InVecTy = Op0->getType();
    3935       34736 :   unsigned MaskNumElts = Mask->getType()->getVectorNumElements();
    3936       17368 :   unsigned InVecNumElts = InVecTy->getVectorNumElements();
    3937             : 
    3938       17368 :   SmallVector<int, 32> Indices;
    3939       17368 :   ShuffleVectorInst::getShuffleMask(Mask, Indices);
    3940             :   assert(MaskNumElts == Indices.size() &&
    3941             :          "Size of Indices not same as number of mask elements?");
    3942             : 
    3943             :   // Canonicalization: If mask does not select elements from an input vector,
    3944             :   // replace that input vector with undef.
    3945       17368 :   bool MaskSelects0 = false, MaskSelects1 = false;
    3946      151691 :   for (unsigned i = 0; i != MaskNumElts; ++i) {
    3947      268646 :     if (Indices[i] == -1)
    3948             :       continue;
    3949      217366 :     if ((unsigned)Indices[i] < InVecNumElts)
    3950             :       MaskSelects0 = true;
    3951             :     else
    3952       20827 :       MaskSelects1 = true;
    3953             :   }
    3954       17368 :   if (!MaskSelects0)
    3955          93 :     Op0 = UndefValue::get(InVecTy);
    3956       17368 :   if (!MaskSelects1)
    3957       12969 :     Op1 = UndefValue::get(InVecTy);
    3958             : 
    3959       34736 :   auto *Op0Const = dyn_cast<Constant>(Op0);
    3960       34736 :   auto *Op1Const = dyn_cast<Constant>(Op1);
    3961             : 
    3962             :   // If all operands are constant, constant fold the shuffle.
    3963       17368 :   if (Op0Const && Op1Const)
    3964         126 :     return ConstantFoldShuffleVectorInstruction(Op0Const, Op1Const, Mask);
    3965             : 
    3966             :   // Canonicalization: if only one input vector is constant, it shall be the
    3967             :   // second one.
    3968       17242 :   if (Op0Const && !Op1Const) {
    3969         144 :     std::swap(Op0, Op1);
    3970         144 :     ShuffleVectorInst::commuteShuffleMask(Indices, InVecNumElts);
    3971             :   }
    3972             : 
    3973             :   // A shuffle of a splat is always the splat itself. Legal if the shuffle's
    3974             :   // value type is same as the input vectors' type.
    3975       17451 :   if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op0))
    3976         500 :     if (isa<UndefValue>(Op1) && RetTy == InVecTy &&
    3977          82 :         OpShuf->getMask()->getSplatValue())
    3978             :       return Op0;
    3979             : 
    3980             :   // Don't fold a shuffle with undef mask elements. This may get folded in a
    3981             :   // better way using demanded bits or other analysis.
    3982             :   // TODO: Should we allow this?
    3983       34474 :   if (find(Indices, -1) != Indices.end())
    3984             :     return nullptr;
    3985             : 
    3986             :   // Check if every element of this shuffle can be mapped back to the
    3987             :   // corresponding element of a single root vector. If so, we don't need this
    3988             :   // shuffle. This handles simple identity shuffles as well as chains of
    3989             :   // shuffles that may widen/narrow and/or move elements across lanes and back.
    3990             :   Value *RootVec = nullptr;
    3991       28539 :   for (unsigned i = 0; i != MaskNumElts; ++i) {
    3992             :     // Note that recursion is limited for each vector element, so if any element
    3993             :     // exceeds the limit, this will fail to simplify.
    3994       20354 :     RootVec =
    3995       40708 :         foldIdentityShuffles(i, Op0, Op1, Indices[i], RootVec, MaxRecurse);
    3996             : 
    3997             :     // We can't replace a widening/narrowing shuffle with one of its operands.
    3998       20354 :     if (!RootVec || RootVec->getType() != RetTy)
    3999             :       return nullptr;
    4000             :   }
    4001             :   return RootVec;
    4002             : }
    4003             : 
    4004             : /// Given operands for a ShuffleVectorInst, fold the result or return null.
    4005       17377 : Value *llvm::SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
    4006             :                                        Type *RetTy, const SimplifyQuery &Q) {
    4007       17377 :   return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy, Q, RecursionLimit);
    4008             : }
    4009             : 
    4010             : /// Given operands for an FAdd, see if we can fold the result.  If not, this
    4011             : /// returns null.
    4012       12902 : static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4013             :                                const SimplifyQuery &Q, unsigned MaxRecurse) {
    4014       12902 :   if (Constant *C = foldOrCommuteConstant(Instruction::FAdd, Op0, Op1, Q))
    4015             :     return C;
    4016             : 
    4017             :   // fadd X, -0 ==> X
    4018       16632 :   if (match(Op1, m_NegZero()))
    4019           3 :     return Op0;
    4020             : 
    4021             :   // fadd X, 0 ==> X, when we know X is not -0
    4022       16906 :   if (match(Op1, m_Zero()) &&
    4023         538 :       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
    4024          28 :     return Op0;
    4025             : 
    4026             :   // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0
    4027             :   //   where nnan and ninf have to occur at least once somewhere in this
    4028             :   //   expression
    4029       12838 :   Value *SubOp = nullptr;
    4030       51352 :   if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0))))
    4031           0 :     SubOp = Op1;
    4032       51352 :   else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1))))
    4033           9 :     SubOp = Op0;
    4034           9 :   if (SubOp) {
    4035           9 :     Instruction *FSub = cast<Instruction>(SubOp);
    4036          18 :     if ((FMF.noNaNs() || FSub->hasNoNaNs()) &&
    4037          15 :         (FMF.noInfs() || FSub->hasNoInfs()))
    4038           4 :       return Constant::getNullValue(Op0->getType());
    4039             :   }
    4040             : 
    4041             :   return nullptr;
    4042             : }
    4043             : 
    4044             : /// Given operands for an FSub, see if we can fold the result.  If not, this
    4045             : /// returns null.
    4046        8651 : static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4047             :                                const SimplifyQuery &Q, unsigned MaxRecurse) {
    4048        8651 :   if (Constant *C = foldOrCommuteConstant(Instruction::FSub, Op0, Op1, Q))
    4049             :     return C;
    4050             : 
    4051             :   // fsub X, 0 ==> X
    4052        9209 :   if (match(Op1, m_Zero()))
    4053          19 :     return Op0;
    4054             : 
    4055             :   // fsub X, -0 ==> X, when we know X is not -0
    4056        9171 :   if (match(Op1, m_NegZero()) &&
    4057           0 :       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
    4058           0 :     return Op0;
    4059             : 
    4060             :   // fsub -0.0, (fsub -0.0, X) ==> X
    4061             :   Value *X;
    4062       26838 :   if (match(Op0, m_NegZero()) && match(Op1, m_FSub(m_NegZero(), m_Value(X))))
    4063           1 :     return X;
    4064             : 
    4065             :   // fsub 0.0, (fsub 0.0, X) ==> X if signed zeros are ignored.
    4066        8951 :   if (FMF.noSignedZeros() && match(Op0, m_AnyZero()) &&
    4067        8765 :       match(Op1, m_FSub(m_AnyZero(), m_Value(X))))
    4068           1 :     return X;
    4069             : 
    4070             :   // fsub nnan x, x ==> 0.0
    4071        8814 :   if (FMF.noNaNs() && Op0 == Op1)
    4072           1 :     return Constant::getNullValue(Op0->getType());
    4073             : 
    4074             :   return nullptr;
    4075             : }
    4076             : 
    4077             : /// Given the operands for an FMul, see if we can fold the result
    4078       13411 : static Value *SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4079             :                                const SimplifyQuery &Q, unsigned MaxRecurse) {
    4080       13411 :   if (Constant *C = foldOrCommuteConstant(Instruction::FMul, Op0, Op1, Q))
    4081             :     return C;
    4082             : 
    4083             :   // fmul X, 1.0 ==> X
    4084       26722 :   if (match(Op1, m_FPOne()))
    4085          23 :     return Op0;
    4086             : 
    4087             :   // fmul nnan nsz X, 0 ==> 0
    4088       15297 :   if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero()))
    4089           6 :     return Op1;
    4090             : 
    4091             :   return nullptr;
    4092             : }
    4093             : 
    4094       12481 : Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4095             :                               const SimplifyQuery &Q) {
    4096       12481 :   return ::SimplifyFAddInst(Op0, Op1, FMF, Q, RecursionLimit);
    4097             : }
    4098             : 
    4099             : 
    4100        8638 : Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4101             :                               const SimplifyQuery &Q) {
    4102        8638 :   return ::SimplifyFSubInst(Op0, Op1, FMF, Q, RecursionLimit);
    4103             : }
    4104             : 
    4105       11913 : Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4106             :                               const SimplifyQuery &Q) {
    4107       11913 :   return ::SimplifyFMulInst(Op0, Op1, FMF, Q, RecursionLimit);
    4108             : }
    4109             : 
    4110        2414 : static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4111             :                                const SimplifyQuery &Q, unsigned) {
    4112        2414 :   if (Constant *C = foldOrCommuteConstant(Instruction::FDiv, Op0, Op1, Q))
    4113             :     return C;
    4114             : 
    4115             :   // undef / X -> undef    (the undef could be a snan).
    4116        4822 :   if (match(Op0, m_Undef()))
    4117             :     return Op0;
    4118             : 
    4119             :   // X / undef -> undef
    4120        4820 :   if (match(Op1, m_Undef()))
    4121             :     return Op1;
    4122             : 
    4123             :   // X / 1.0 -> X
    4124        4818 :   if (match(Op1, m_FPOne()))
    4125           1 :     return Op0;
    4126             : 
    4127             :   // 0 / X -> 0
    4128             :   // Requires that NaNs are off (X could be zero) and signed zeroes are
    4129             :   // ignored (X could be positive or negative, so the output sign is unknown).
    4130        2851 :   if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero()))
    4131           1 :     return Op0;
    4132             : 
    4133        2407 :   if (FMF.noNaNs()) {
    4134             :     // X / X -> 1.0 is legal when NaNs are ignored.
    4135         309 :     if (Op0 == Op1)
    4136           1 :       return ConstantFP::get(Op0->getType(), 1.0);
    4137             : 
    4138             :     // -X /  X -> -1.0 and
    4139             :     //  X / -X -> -1.0 are legal when NaNs are ignored.
    4140             :     // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored.
    4141         311 :     if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) &&
    4142         614 :          BinaryOperator::getFNegArgument(Op0) == Op1) ||
    4143         309 :         (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) &&
    4144           3 :          BinaryOperator::getFNegArgument(Op1) == Op0))
    4145           4 :       return ConstantFP::get(Op0->getType(), -1.0);
    4146             :   }
    4147             : 
    4148             :   return nullptr;
    4149             : }
    4150             : 
    4151        2405 : Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4152             :                               const SimplifyQuery &Q) {
    4153        2405 :   return ::SimplifyFDivInst(Op0, Op1, FMF, Q, RecursionLimit);
    4154             : }
    4155             : 
    4156          72 : static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4157             :                                const SimplifyQuery &Q, unsigned) {
    4158          72 :   if (Constant *C = foldOrCommuteConstant(Instruction::FRem, Op0, Op1, Q))
    4159             :     return C;
    4160             : 
    4161             :   // undef % X -> undef    (the undef could be a snan).
    4162         142 :   if (match(Op0, m_Undef()))
    4163             :     return Op0;
    4164             : 
    4165             :   // X % undef -> undef
    4166         142 :   if (match(Op1, m_Undef()))
    4167             :     return Op1;
    4168             : 
    4169             :   // 0 % X -> 0
    4170             :   // Requires that NaNs are off (X could be zero) and signed zeroes are
    4171             :   // ignored (X could be positive or negative, so the output sign is unknown).
    4172          71 :   if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero()))
    4173           0 :     return Op0;
    4174             : 
    4175             :   return nullptr;
    4176             : }
    4177             : 
    4178          72 : Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
    4179             :                               const SimplifyQuery &Q) {
    4180          72 :   return ::SimplifyFRemInst(Op0, Op1, FMF, Q, RecursionLimit);
    4181             : }
    4182             : 
    4183             : //=== Helper functions for higher up the class hierarchy.
    4184             : 
    4185             : /// Given operands for a BinaryOperator, see if we can fold the result.
    4186             : /// If not, this returns null.
    4187      431076 : static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
    4188             :                             const SimplifyQuery &Q, unsigned MaxRecurse) {
    4189      431076 :   switch (Opcode) {
    4190      248681 :   case Instruction::Add:
    4191      248681 :     return SimplifyAddInst(LHS, RHS, false, false, Q, MaxRecurse);
    4192        7178 :   case Instruction::Sub:
    4193        7178 :     return SimplifySubInst(LHS, RHS, false, false, Q, MaxRecurse);
    4194       55809 :   case Instruction::Mul:
    4195       55809 :     return SimplifyMulInst(LHS, RHS, Q, MaxRecurse);
    4196         160 :   case Instruction::SDiv:
    4197         160 :     return SimplifySDivInst(LHS, RHS, Q, MaxRecurse);
    4198         215 :   case Instruction::UDiv:
    4199         215 :     return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse);
    4200         283 :   case Instruction::SRem:
    4201         283 :     return SimplifySRemInst(LHS, RHS, Q, MaxRecurse);
    4202        1332 :   case Instruction::URem:
    4203        1332 :     return SimplifyURemInst(LHS, RHS, Q, MaxRecurse);
    4204        9530 :   case Instruction::Shl:
    4205        9530 :     return SimplifyShlInst(LHS, RHS, false, false, Q, MaxRecurse);
    4206        2900 :   case Instruction::LShr:
    4207        2900 :     return SimplifyLShrInst(LHS, RHS, false, Q, MaxRecurse);
    4208         176 :   case Instruction::AShr:
    4209         176 :     return SimplifyAShrInst(LHS, RHS, false, Q, MaxRecurse);
    4210       31239 :   case Instruction::And:
    4211       31239 :     return SimplifyAndInst(LHS, RHS, Q, MaxRecurse);
    4212       55287 :   case Instruction::Or:
    4213       55287 :     return SimplifyOrInst(LHS, RHS, Q, MaxRecurse);
    4214       16347 :   case Instruction::Xor:
    4215       16347 :     return SimplifyXorInst(LHS, RHS, Q, MaxRecurse);
    4216         420 :   case Instruction::FAdd:
    4217         420 :     return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
    4218          12 :   case Instruction::FSub:
    4219          12 :     return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
    4220        1498 :   case Instruction::FMul:
    4221        1498 :     return SimplifyFMulInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
    4222           9 :   case Instruction::FDiv:
    4223           9 :     return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
    4224           0 :   case Instruction::FRem:
    4225           0 :     return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
    4226           0 :   default:
    4227           0 :     llvm_unreachable("Unexpected opcode");
    4228             :   }
    4229             : }
    4230             : 
    4231             : /// Given operands for a BinaryOperator, see if we can fold the result.
    4232             : /// If not, this returns null.
    4233             : /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
    4234             : /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
    4235           2 : static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
    4236             :                               const FastMathFlags &FMF, const SimplifyQuery &Q,
    4237             :                               unsigned MaxRecurse) {
    4238           2 :   switch (Opcode) {
    4239           1 :   case Instruction::FAdd:
    4240           1 :     return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse);
    4241           1 :   case Instruction::FSub:
    4242           1 :     return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse);
    4243           0 :   case Instruction::FMul:
    4244           0 :     return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse);
    4245           0 :   case Instruction::FDiv:
    4246           0 :     return SimplifyFDivInst(LHS, RHS, FMF, Q, MaxRecurse);
    4247           0 :   default:
    4248           0 :     return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse);
    4249             :   }
    4250             : }
    4251             : 
    4252       74275 : Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
    4253             :                            const SimplifyQuery &Q) {
    4254       74275 :   return ::SimplifyBinOp(Opcode, LHS, RHS, Q, RecursionLimit);
    4255             : }
    4256             : 
    4257           2 : Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
    4258             :                              FastMathFlags FMF, const SimplifyQuery &Q) {
    4259           2 :   return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Q, RecursionLimit);
    4260             : }
    4261             : 
    4262             : /// Given operands for a CmpInst, see if we can fold the result.
    4263       89786 : static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
    4264             :                               const SimplifyQuery &Q, unsigned MaxRecurse) {
    4265       89786 :   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
    4266       89399 :     return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
    4267         387 :   return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse);
    4268             : }
    4269             : 
    4270        6222 : Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
    4271             :                              const SimplifyQuery &Q) {
    4272        6222 :   return ::SimplifyCmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
    4273             : }
    4274             : 
    4275             : static bool IsIdempotent(Intrinsic::ID ID) {
    4276       24283 :   switch (ID) {
    4277             :   default: return false;
    4278             : 
    4279             :   // Unary idempotent: f(f(x)) = f(x)
    4280             :   case Intrinsic::fabs:
    4281             :   case Intrinsic::floor:
    4282             :   case Intrinsic::ceil:
    4283             :   case Intrinsic::trunc:
    4284             :   case Intrinsic::rint:
    4285             :   case Intrinsic::nearbyint:
    4286             :   case Intrinsic::round:
    4287             :   case Intrinsic::canonicalize:
    4288             :     return true;
    4289             :   }
    4290             : }
    4291             : 
    4292           9 : static Value *SimplifyRelativeLoad(Constant *Ptr, Constant *Offset,
    4293             :                                    const DataLayout &DL) {
    4294             :   GlobalValue *PtrSym;
    4295          18 :   APInt PtrOffset;
    4296           9 :   if (!IsConstantOffsetFromGlobal(Ptr, PtrSym, PtrOffset, DL))
    4297             :     return nullptr;
    4298             : 
    4299           8 :   Type *Int8PtrTy = Type::getInt8PtrTy(Ptr->getContext());
    4300           8 :   Type *Int32Ty = Type::getInt32Ty(Ptr->getContext());
    4301           8 :   Type *Int32PtrTy = Int32Ty->getPointerTo();
    4302           8 :   Type *Int64Ty = Type::getInt64Ty(Ptr->getContext());
    4303             : 
    4304           8 :   auto *OffsetConstInt = dyn_cast<ConstantInt>(Offset);
    4305          16 :   if (!OffsetConstInt || OffsetConstInt->getType()->getBitWidth() > 64)
    4306             :     return nullptr;
    4307             : 
    4308           8 :   uint64_t OffsetInt = OffsetConstInt->getSExtValue();
    4309           8 :   if (OffsetInt % 4 != 0)
    4310             :     return nullptr;
    4311             : 
    4312          14 :   Constant *C = ConstantExpr::getGetElementPtr(
    4313             :       Int32Ty, ConstantExpr::getBitCast(Ptr, Int32PtrTy),
    4314           7 :       ConstantInt::get(Int64Ty, OffsetInt / 4));
    4315           7 :   Constant *Loaded = ConstantFoldLoadFromConstPtr(C, Int32Ty, DL);
    4316           7 :   if (!Loaded)
    4317             :     return nullptr;
    4318             : 
    4319           7 :   auto *LoadedCE = dyn_cast<ConstantExpr>(Loaded);
    4320             :   if (!LoadedCE)
    4321             :     return nullptr;
    4322             : 
    4323           7 :   if (LoadedCE->getOpcode() == Instruction::Trunc) {
    4324           6 :     LoadedCE = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
    4325             :     if (!LoadedCE)
    4326             :       return nullptr;
    4327             :   }
    4328             : 
    4329           7 :   if (LoadedCE->getOpcode() != Instruction::Sub)
    4330             :     return nullptr;
    4331             : 
    4332          11 :   auto *LoadedLHS = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
    4333           5 :   if (!LoadedLHS || LoadedLHS->getOpcode() != Instruction::PtrToInt)
    4334             :     return nullptr;
    4335           5 :   auto *LoadedLHSPtr = LoadedLHS->getOperand(0);
    4336             : 
    4337           5 :   Constant *LoadedRHS = LoadedCE->getOperand(1);
    4338             :   GlobalValue *LoadedRHSSym;
    4339           5 :   APInt LoadedRHSOffset;
    4340           5 :   if (!IsConstantOffsetFromGlobal(LoadedRHS, LoadedRHSSym, LoadedRHSOffset,
    4341           4 :                                   DL) ||
    4342           9 :       PtrSym != LoadedRHSSym || PtrOffset != LoadedRHSOffset)
    4343             :     return nullptr;
    4344             : 
    4345           4 :   return ConstantExpr::getBitCast(LoadedLHSPtr, Int8PtrTy);
    4346             : }
    4347             : 
    4348        1036 : static bool maskIsAllZeroOrUndef(Value *Mask) {
    4349          17 :   auto *ConstMask = dyn_cast<Constant>(Mask);
    4350             :   if (!ConstMask)
    4351             :     return false;
    4352          32 :   if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
    4353             :     return true;
    4354          42 :   for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
    4355             :        ++I) {
    4356          29 :     if (auto *MaskElt = ConstMask->getAggregateElement(I))
    4357          42 :       if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
    4358          16 :         continue;
    4359             :     return false;
    4360             :   }
    4361             :   return true;
    4362             : }
    4363             : 
    4364             : template <typename IterTy>
    4365     1149237 : static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd,
    4366             :                                 const SimplifyQuery &Q, unsigned MaxRecurse) {
    4367     1149237 :   Intrinsic::ID IID = F->getIntrinsicID();
    4368     1149237 :   unsigned NumOperands = std::distance(ArgBegin, ArgEnd);
    4369             : 
    4370             :   // Unary Ops
    4371     1149237 :   if (NumOperands == 1) {
    4372             :     // Perform idempotent optimizations
    4373        5169 :     if (IsIdempotent(IID)) {
    4374         315 :       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) {
    4375         315 :         if (II->getIntrinsicID() == IID)
    4376             :           return II;
    4377             :       }
    4378             :     }
    4379             : 
    4380       24265 :     switch (IID) {
    4381        2145 :     case Intrinsic::fabs: {
    4382        2145 :       if (SignBitMustBeZero(*ArgBegin, Q.TLI))
    4383          10 :         return *ArgBegin;
    4384             :       return nullptr;
    4385             :     }
    4386             :     default:
    4387             :       return nullptr;
    4388             :     }
    4389             :   }
    4390             : 
    4391             :   // Binary Ops
    4392     1124954 :   if (NumOperands == 2) {
    4393      769417 :     Value *LHS = *ArgBegin;
    4394      769417 :     Value *RHS = *(ArgBegin + 1);
    4395      769417 :     Type *ReturnType = F->getReturnType();
    4396             : 
    4397      769417 :     switch (IID) {
    4398         490 :     case Intrinsic::usub_with_overflow:
    4399             :     case Intrinsic::ssub_with_overflow: {
    4400             :       // X - X -> { 0, false }
    4401         490 :       if (LHS == RHS)
    4402           4 :         return Constant::getNullValue(ReturnType);
    4403             : 
    4404             :       // X - undef -> undef
    4405             :       // undef - X -> undef
    4406        1454 :       if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
    4407           8 :         return UndefValue::get(ReturnType);
    4408             : 
    4409             :       return nullptr;
    4410             :     }
    4411         511 :     case Intrinsic::uadd_with_overflow:
    4412             :     case Intrinsic::sadd_with_overflow: {
    4413             :       // X + undef -> undef
    4414        1528 :       if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
    4415           9 :         return UndefValue::get(ReturnType);
    4416             : 
    4417             :       return nullptr;
    4418             :     }
    4419             :     case Intrinsic::umul_with_overflow:
    4420             :     case Intrinsic::smul_with_overflow: {
    4421             :       // 0 * X -> { 0, false }
    4422             :       // X * 0 -> { 0, false }
    4423         152 :       if (match(LHS, m_Zero()) || match(RHS, m_Zero()))
    4424           9 :         return Constant::getNullValue(ReturnType);
    4425             : 
    4426             :       // undef * X -> { 0, false }
    4427             :       // X * undef -> { 0, false }
    4428         320 :       if (match(LHS, m_Undef()) || match(RHS, m_Undef()))
    4429           8 :         return Constant::getNullValue(ReturnType);
    4430             : 
    4431             :       return nullptr;
    4432             :     }
    4433           9 :     case Intrinsic::load_relative: {
    4434          18 :       Constant *C0 = dyn_cast<Constant>(LHS);
    4435          18 :       Constant *C1 = dyn_cast<Constant>(RHS);
    4436           9 :       if (C0 && C1)
    4437           9 :         return SimplifyRelativeLoad(C0, C1, Q.DL);
    4438             :       return nullptr;
    4439             :     }
    4440             :     default:
    4441             :       return nullptr;
    4442             :     }
    4443             :   }
    4444             : 
    4445             :   // Simplify calls to llvm.masked.load.*
    4446      355537 :   switch (IID) {
    4447        1036 :   case Intrinsic::masked_load: {
    4448        1036 :     Value *MaskArg = ArgBegin[2];
    4449        1036 :     Value *PassthruArg = ArgBegin[3];
    4450             :     // If the mask is all zeros or undef, the "passthru" argument is the result.
    4451        1036 :     if (maskIsAllZeroOrUndef(MaskArg))
    4452             :       return PassthruArg;
    4453             :     return nullptr;
    4454             :   }
    4455             :   default:
    4456             :     return nullptr;
    4457             :   }
    4458             : }
    4459             : 
    4460             : template <typename IterTy>
    4461     3610398 : static Value *SimplifyCall(ImmutableCallSite CS, Value *V, IterTy ArgBegin,
    4462             :                            IterTy ArgEnd, const SimplifyQuery &Q,
    4463             :                            unsigned MaxRecurse) {
    4464     3610398 :   Type *Ty = V->getType();
    4465     3610398 :   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
    4466     3610398 :     Ty = PTy->getElementType();
    4467     3610398 :   FunctionType *FTy = cast<FunctionType>(Ty);
    4468             : 
    4469             :   // call undef -> undef
    4470             :   // call null -> undef
    4471    10831188 :   if (isa<UndefValue>(V) || isa<ConstantPointerNull>(V))
    4472          17 :     return UndefValue::get(FTy->getReturnType());
    4473             : 
    4474     7196497 :   Function *F = dyn_cast<Function>(V);
    4475             :   if (!F)
    4476             :     return nullptr;
    4477             : 
    4478     3586116 :   if (F->isIntrinsic())
    4479     1149237 :     if (Value *Ret = SimplifyIntrinsic(F, ArgBegin, ArgEnd, Q, MaxRecurse))
    4480             :       return Ret;
    4481             : 
    4482     3586042 :   if (!canConstantFoldCallTo(CS, F))
    4483             :     return nullptr;
    4484             : 
    4485       21273 :   SmallVector<Constant *, 4> ConstantArgs;
    4486       21273 :   ConstantArgs.reserve(ArgEnd - ArgBegin);
    4487       22084 :   for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) {
    4488       21989 :     Constant *C = dyn_cast<Constant>(*I);
    4489       21989 :     if (!C)
    4490       21178 :       return nullptr;
    4491         811 :     ConstantArgs.push_back(C);
    4492             :   }
    4493             : 
    4494         190 :   return ConstantFoldCall(CS, F, ConstantArgs, Q.TLI);
    4495             : }
    4496             : 
    4497     3610398 : Value *llvm::SimplifyCall(ImmutableCallSite CS, Value *V,
    4498             :                           User::op_iterator ArgBegin, User::op_iterator ArgEnd,
    4499             :                           const SimplifyQuery &Q) {
    4500     3610398 :   return ::SimplifyCall(CS, V, ArgBegin, ArgEnd, Q, RecursionLimit);
    4501             : }
    4502             : 
    4503           0 : Value *llvm::SimplifyCall(ImmutableCallSite CS, Value *V,
    4504             :                           ArrayRef<Value *> Args, const SimplifyQuery &Q) {
    4505           0 :   return ::SimplifyCall(CS, V, Args.begin(), Args.end(), Q, RecursionLimit);
    4506             : }
    4507             : 
    4508             : /// See if we can compute a simplified version of this instruction.
    4509             : /// If not, this returns null.
    4510             : 
    4511    12146086 : Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
    4512             :                                  OptimizationRemarkEmitter *ORE) {
    4513    12146086 :   const SimplifyQuery Q = SQ.CxtI ? SQ : SQ.getWithInstruction(I);
    4514             :   Value *Result;
    4515             : 
    4516    12146086 :   switch (I->getOpcode()) {
    4517     5740456 :   default:
    4518     5740456 :     Result = ConstantFoldInstruction(I, Q.DL, Q.TLI);
    4519     5740456 :     break;
    4520        8917 :   case Instruction::FAdd:
    4521       26751 :     Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1),
    4522             :                               I->getFastMathFlags(), Q);
    4523        8917 :     break;
    4524     1442384 :   case Instruction::Add:
    4525     5769536 :     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
    4526     1442384 :                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
    4527     1442384 :                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
    4528     1442384 :     break;
    4529        6004 :   case Instruction::FSub:
    4530       18012 :     Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1),
    4531             :                               I->getFastMathFlags(), Q);
    4532        6004 :     break;
    4533       18552 :   case Instruction::Sub:
    4534       74208 :     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
    4535       18552 :                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
    4536       18552 :                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
    4537       18552 :     break;
    4538        7988 :   case Instruction::FMul:
    4539       23964 :     Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1),
    4540             :                               I->getFastMathFlags(), Q);
    4541        7988 :     break;
    4542        6560 :   case Instruction::Mul:
    4543       19680 :     Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), Q);
    4544        6560 :     break;
    4545        2475 :   case Instruction::SDiv:
    4546        7425 :     Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), Q);
    4547        2475 :     break;
    4548        1339 :   case Instruction::UDiv:
    4549        4017 :     Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), Q);
    4550        1339 :     break;
    4551        1351 :   case Instruction::FDiv:
    4552        4053 :     Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1),
    4553             :                               I->getFastMathFlags(), Q);
    4554        1351 :     break;
    4555         589 :   case Instruction::SRem:
    4556        1767 :     Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), Q);
    4557         589 :     break;
    4558        1616 :   case Instruction::URem:
    4559        4848 :     Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), Q);
    4560        1616 :     break;
    4561          69 :   case Instruction::FRem:
    4562         207 :     Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1),
    4563             :                               I->getFastMathFlags(), Q);
    4564          69 :     break;
    4565       12129 :   case Instruction::Shl:
    4566       48516 :     Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
    4567       12129 :                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
    4568       12129 :                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
    4569       12129 :     break;
    4570        7980 :   case Instruction::LShr:
    4571       23940 :     Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
    4572        7980 :                               cast<BinaryOperator>(I)->isExact(), Q);
    4573        7980 :     break;
    4574        6715 :   case Instruction::AShr:
    4575       20145 :     Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
    4576        6715 :                               cast<BinaryOperator>(I)->isExact(), Q);
    4577        6715 :     break;
    4578       19804 :   case Instruction::And:
    4579       59412 :     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), Q);
    4580       19804 :     break;
    4581       11843 :   case Instruction::Or:
    4582       35529 :     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), Q);
    4583       11843 :     break;
    4584       15570 :   case Instruction::Xor:
    4585       46710 :     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), Q);
    4586       15570 :     break;
    4587      195519 :   case Instruction::ICmp:
    4588      977595 :     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
    4589             :                               I->getOperand(0), I->getOperand(1), Q);
    4590      195519 :     break;
    4591        3491 :   case Instruction::FCmp:
    4592        3491 :     Result =
    4593       17455 :         SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), I->getOperand(0),
    4594             :                          I->getOperand(1), I->getFastMathFlags(), Q);
    4595        3491 :     break;
    4596      143185 :   case Instruction::Select:
    4597      572740 :     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
    4598             :                                 I->getOperand(2), Q);
    4599      143185 :     break;
    4600      514402 :   case Instruction::GetElementPtr: {
    4601     2572010 :     SmallVector<Value *, 8> Ops(I->op_begin(), I->op_end());
    4602     1028804 :     Result = SimplifyGEPInst(cast<GetElementPtrInst>(I)->getSourceElementType(),
    4603             :                              Ops, Q);
    4604             :     break;
    4605             :   }
    4606       19199 :   case Instruction::InsertValue: {
    4607       19199 :     InsertValueInst *IV = cast<InsertValueInst>(I);
    4608       57597 :     Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
    4609             :                                      IV->getInsertedValueOperand(),
    4610             :                                      IV->getIndices(), Q);
    4611       19199 :     break;
    4612             :   }
    4613      195495 :   case Instruction::ExtractValue: {
    4614      195495 :     auto *EVI = cast<ExtractValueInst>(I);
    4615      390990 :     Result = SimplifyExtractValueInst(EVI->getAggregateOperand(),
    4616             :                                       EVI->getIndices(), Q);
    4617      195495 :     break;
    4618             :   }
    4619       11223 :   case Instruction::ExtractElement: {
    4620       11223 :     auto *EEI = cast<ExtractElementInst>(I);
    4621       22446 :     Result = SimplifyExtractElementInst(EEI->getVectorOperand(),
    4622             :                                         EEI->getIndexOperand(), Q);
    4623       11223 :     break;
    4624             :   }
    4625        7626 :   case Instruction::ShuffleVector: {
    4626        7626 :     auto *SVI = cast<ShuffleVectorInst>(I);
    4627       22878 :     Result = SimplifyShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1),
    4628        7626 :                                        SVI->getMask(), SVI->getType(), Q);
    4629        7626 :     break;
    4630             :   }
    4631     1757797 :   case Instruction::PHI:
    4632     1757797 :     Result = SimplifyPHINode(cast<PHINode>(I), Q);
    4633     1757797 :     break;
    4634     1108739 :   case Instruction::Call: {
    4635     2217478 :     CallSite CS(cast<CallInst>(I));
    4636     4434956 :     Result = SimplifyCall(CS, CS.getCalledValue(), CS.arg_begin(), CS.arg_end(),
    4637             :                           Q);
    4638             :     break;
    4639             :   }
    4640             : #define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc:
    4641             : #include "llvm/IR/Instruction.def"
    4642             : #undef HANDLE_CAST_INST
    4643      623163 :     Result =
    4644     1869489 :         SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(), Q);
    4645      623163 :     break;
    4646             :   case Instruction::Alloca:
    4647             :     // No simplifications for Alloca and it can't be constant folded.
    4648             :     Result = nullptr;
    4649             :     break;
    4650             :   }
    4651             : 
    4652             :   // In general, it is possible for computeKnownBits to determine all bits in a
    4653             :   // value even when the operands are not all constants.
    4654    23941382 :   if (!Result && I->getType()->isIntOrIntVectorTy()) {
    4655     8506484 :     KnownBits Known = computeKnownBits(I, Q.DL, /*Depth*/ 0, Q.AC, I, Q.DT, ORE);
    4656     4253242 :     if (Known.isConstant())
    4657          94 :       Result = ConstantInt::get(I->getType(), Known.getConstant());
    4658             :   }
    4659             : 
    4660             :   /// If called on unreachable code, the above logic may report that the
    4661             :   /// instruction simplified to itself.  Make life easier for users by
    4662             :   /// detecting that case here, returning a safe value instead.
    4663    12146086 :   return Result == I ? UndefValue::get(I->getType()) : Result;
    4664             : }
    4665             : 
    4666             : /// \brief Implementation of recursive simplification through an instruction's
    4667             : /// uses.
    4668             : ///
    4669             : /// This is the common implementation of the recursive simplification routines.
    4670             : /// If we have a pre-simplified value in 'SimpleV', that is forcibly used to
    4671             : /// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of
    4672             : /// instructions to process and attempt to simplify it using
    4673             : /// InstructionSimplify.
    4674             : ///
    4675             : /// This routine returns 'true' only when *it* simplifies something. The passed
    4676             : /// in simplified value does not count toward this.
    4677          72 : static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
    4678             :                                               const TargetLibraryInfo *TLI,
    4679             :                                               const DominatorTree *DT,
    4680             :                                               AssumptionCache *AC) {
    4681          72 :   bool Simplified = false;
    4682         144 :   SmallSetVector<Instruction *, 8> Worklist;
    4683         144 :   const DataLayout &DL = I->getModule()->getDataLayout();
    4684             : 
    4685             :   // If we have an explicit value to collapse to, do that round of the
    4686             :   // simplification loop by hand initially.
    4687          72 :   if (SimpleV) {
    4688         358 :     for (User *U : I->users())
    4689          71 :       if (U != I)
    4690          71 :         Worklist.insert(cast<Instruction>(U));
    4691             : 
    4692             :     // Replace the instruction with its simplified value.
    4693          72 :     I->replaceAllUsesWith(SimpleV);
    4694             : 
    4695             :     // Gracefully handle edge cases where the instruction is not wired into any
    4696             :     // parent block.
    4697         288 :     if (I->getParent() && !I->isEHPad() && !isa<TerminatorInst>(I) &&
    4698          72 :         !I->mayHaveSideEffects())
    4699          72 :       I->eraseFromParent();
    4700             :   } else {
    4701           0 :     Worklist.insert(I);
    4702             :   }
    4703             : 
    4704             :   // Note that we must test the size on each iteration, the worklist can grow.
    4705         498 :   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
    4706         236 :     I = Worklist[Idx];
    4707             : 
    4708             :     // See if this instruction simplifies.
    4709         118 :     SimpleV = SimplifyInstruction(I, {DL, TLI, DT, AC});
    4710         118 :     if (!SimpleV)
    4711          71 :       continue;
    4712             : 
    4713          47 :     Simplified = true;
    4714             : 
    4715             :     // Stash away all the uses of the old instruction so we can check them for
    4716             :     // recursive simplifications after a RAUW. This is cheaper than checking all
    4717             :     // uses of To on the recursive step in most cases.
    4718         235 :     for (User *U : I->users())
    4719          47 :       Worklist.insert(cast<Instruction>(U));
    4720             : 
    4721             :     // Replace the instruction with its simplified value.
    4722          47 :     I->replaceAllUsesWith(SimpleV);
    4723             : 
    4724             :     // Gracefully handle edge cases where the instruction is not wired into any
    4725             :     // parent block.
    4726         188 :     if (I->getParent() && !I->isEHPad() && !isa<TerminatorInst>(I) &&
    4727          47 :         !I->mayHaveSideEffects())
    4728          47 :       I->eraseFromParent();
    4729             :   }
    4730         144 :   return Simplified;
    4731             : }
    4732             : 
    4733           0 : bool llvm::recursivelySimplifyInstruction(Instruction *I,
    4734             :                                           const TargetLibraryInfo *TLI,
    4735             :                                           const DominatorTree *DT,
    4736             :                                           AssumptionCache *AC) {
    4737           0 :   return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC);
    4738             : }
    4739             : 
    4740          72 : bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
    4741             :                                          const TargetLibraryInfo *TLI,
    4742             :                                          const DominatorTree *DT,
    4743             :                                          AssumptionCache *AC) {
    4744             :   assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!");
    4745             :   assert(SimpleV && "Must provide a simplified value.");
    4746          72 :   return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC);
    4747             : }
    4748             : 
    4749             : namespace llvm {
    4750       72602 : const SimplifyQuery getBestSimplifyQuery(Pass &P, Function &F) {
    4751       72602 :   auto *DTWP = P.getAnalysisIfAvailable<DominatorTreeWrapperPass>();
    4752       78124 :   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
    4753       72602 :   auto *TLIWP = P.getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
    4754      145204 :   auto *TLI = TLIWP ? &TLIWP->getTLI() : nullptr;
    4755       72602 :   auto *ACWP = P.getAnalysisIfAvailable<AssumptionCacheTracker>();
    4756       72602 :   auto *AC = ACWP ? &ACWP->getAssumptionCache(F) : nullptr;
    4757      145204 :   return {F.getParent()->getDataLayout(), TLI, DT, AC};
    4758             : }
    4759             : 
    4760          59 : const SimplifyQuery getBestSimplifyQuery(LoopStandardAnalysisResults &AR,
    4761             :                                          const DataLayout &DL) {
    4762         118 :   return {DL, &AR.TLI, &AR.DT, &AR.AC};
    4763             : }
    4764             : 
    4765             : template <class T, class... TArgs>
    4766         220 : const SimplifyQuery getBestSimplifyQuery(AnalysisManager<T, TArgs...> &AM,
    4767             :                                          Function &F) {
    4768         220 :   auto *DT = AM.template getCachedResult<DominatorTreeAnalysis>(F);
    4769         220 :   auto *TLI = AM.template getCachedResult<TargetLibraryAnalysis>(F);
    4770         220 :   auto *AC = AM.template getCachedResult<AssumptionAnalysis>(F);
    4771         440 :   return {F.getParent()->getDataLayout(), TLI, DT, AC};
    4772             : }
    4773             : template const SimplifyQuery getBestSimplifyQuery(AnalysisManager<Function> &,
    4774             :                                                   Function &);
    4775             : }

Generated by: LCOV version 1.13