LCOV - code coverage report
Current view: top level - lib/Transforms/InstCombine - InstCombineAndOrXor.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1102 1204 91.5 %
Date: 2017-04-27 17:53:54 Functions: 32 32 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- InstCombineAndOrXor.cpp --------------------------------------------===//
       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 the visitAnd, visitOr, and visitXor functions.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "InstCombineInternal.h"
      15             : #include "llvm/Analysis/InstructionSimplify.h"
      16             : #include "llvm/IR/ConstantRange.h"
      17             : #include "llvm/IR/Intrinsics.h"
      18             : #include "llvm/IR/PatternMatch.h"
      19             : #include "llvm/Transforms/Utils/CmpInstAnalysis.h"
      20             : #include "llvm/Transforms/Utils/Local.h"
      21             : using namespace llvm;
      22             : using namespace PatternMatch;
      23             : 
      24             : #define DEBUG_TYPE "instcombine"
      25             : 
      26       62443 : static inline Value *dyn_castNotVal(Value *V) {
      27             :   // If this is not(not(x)) don't return that this is a not: we want the two
      28             :   // not's to be folded first.
      29       62443 :   if (BinaryOperator::isNot(V)) {
      30         817 :     Value *Operand = BinaryOperator::getNotArgument(V);
      31         817 :     if (!IsFreeToInvert(Operand, Operand->hasOneUse()))
      32             :       return Operand;
      33             :   }
      34             : 
      35             :   // Constants can be considered to be not'ed values...
      36       61630 :   if (ConstantInt *C = dyn_cast<ConstantInt>(V))
      37          96 :     return ConstantInt::get(C->getType(), ~C->getValue());
      38             :   return nullptr;
      39             : }
      40             : 
      41             : /// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into
      42             : /// a four bit mask.
      43             : static unsigned getFCmpCode(FCmpInst::Predicate CC) {
      44             :   assert(FCmpInst::FCMP_FALSE <= CC && CC <= FCmpInst::FCMP_TRUE &&
      45             :          "Unexpected FCmp predicate!");
      46             :   // Take advantage of the bit pattern of FCmpInst::Predicate here.
      47             :   //                                                 U L G E
      48             :   static_assert(FCmpInst::FCMP_FALSE ==  0, "");  // 0 0 0 0
      49             :   static_assert(FCmpInst::FCMP_OEQ   ==  1, "");  // 0 0 0 1
      50             :   static_assert(FCmpInst::FCMP_OGT   ==  2, "");  // 0 0 1 0
      51             :   static_assert(FCmpInst::FCMP_OGE   ==  3, "");  // 0 0 1 1
      52             :   static_assert(FCmpInst::FCMP_OLT   ==  4, "");  // 0 1 0 0
      53             :   static_assert(FCmpInst::FCMP_OLE   ==  5, "");  // 0 1 0 1
      54             :   static_assert(FCmpInst::FCMP_ONE   ==  6, "");  // 0 1 1 0
      55             :   static_assert(FCmpInst::FCMP_ORD   ==  7, "");  // 0 1 1 1
      56             :   static_assert(FCmpInst::FCMP_UNO   ==  8, "");  // 1 0 0 0
      57             :   static_assert(FCmpInst::FCMP_UEQ   ==  9, "");  // 1 0 0 1
      58             :   static_assert(FCmpInst::FCMP_UGT   == 10, "");  // 1 0 1 0
      59             :   static_assert(FCmpInst::FCMP_UGE   == 11, "");  // 1 0 1 1
      60             :   static_assert(FCmpInst::FCMP_ULT   == 12, "");  // 1 1 0 0
      61             :   static_assert(FCmpInst::FCMP_ULE   == 13, "");  // 1 1 0 1
      62             :   static_assert(FCmpInst::FCMP_UNE   == 14, "");  // 1 1 1 0
      63             :   static_assert(FCmpInst::FCMP_TRUE  == 15, "");  // 1 1 1 1
      64             :   return CC;
      65             : }
      66             : 
      67             : /// This is the complement of getICmpCode, which turns an opcode and two
      68             : /// operands into either a constant true or false, or a brand new ICmp
      69             : /// instruction. The sign is passed in to determine which kind of predicate to
      70             : /// use in the new icmp instruction.
      71           5 : static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
      72             :                               InstCombiner::BuilderTy *Builder) {
      73             :   ICmpInst::Predicate NewPred;
      74           5 :   if (Value *NewConstant = getICmpValue(Sign, Code, LHS, RHS, NewPred))
      75             :     return NewConstant;
      76           4 :   return Builder->CreateICmp(NewPred, LHS, RHS);
      77             : }
      78             : 
      79             : /// This is the complement of getFCmpCode, which turns an opcode and two
      80             : /// operands into either a FCmp instruction, or a true/false constant.
      81         211 : static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS,
      82             :                            InstCombiner::BuilderTy *Builder) {
      83         211 :   const auto Pred = static_cast<FCmpInst::Predicate>(Code);
      84             :   assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE &&
      85             :          "Unexpected FCmp predicate!");
      86         211 :   if (Pred == FCmpInst::FCMP_FALSE)
      87          25 :     return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
      88         186 :   if (Pred == FCmpInst::FCMP_TRUE)
      89          26 :     return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1);
      90         160 :   return Builder->CreateFCmp(Pred, LHS, RHS);
      91             : }
      92             : 
      93             : /// \brief Transform BITWISE_OP(BSWAP(A),BSWAP(B)) to BSWAP(BITWISE_OP(A, B))
      94             : /// \param I Binary operator to transform.
      95             : /// \return Pointer to node that must replace the original binary operator, or
      96             : ///         null pointer if no transformation was made.
      97       78865 : Value *InstCombiner::SimplifyBSwap(BinaryOperator &I) {
      98      157730 :   IntegerType *ITy = dyn_cast<IntegerType>(I.getType());
      99             : 
     100             :   // Can't do vectors.
     101      157730 :   if (I.getType()->isVectorTy())
     102             :     return nullptr;
     103             : 
     104             :   // Can only do bitwise ops.
     105      145042 :   if (!I.isBitwiseLogicOp())
     106             :     return nullptr;
     107             : 
     108       72521 :   Value *OldLHS = I.getOperand(0);
     109       72521 :   Value *OldRHS = I.getOperand(1);
     110       72521 :   ConstantInt *ConstLHS = dyn_cast<ConstantInt>(OldLHS);
     111       72521 :   ConstantInt *ConstRHS = dyn_cast<ConstantInt>(OldRHS);
     112       72521 :   IntrinsicInst *IntrLHS = dyn_cast<IntrinsicInst>(OldLHS);
     113       72521 :   IntrinsicInst *IntrRHS = dyn_cast<IntrinsicInst>(OldRHS);
     114       73113 :   bool IsBswapLHS = (IntrLHS && IntrLHS->getIntrinsicID() == Intrinsic::bswap);
     115       72532 :   bool IsBswapRHS = (IntrRHS && IntrRHS->getIntrinsicID() == Intrinsic::bswap);
     116             : 
     117       72521 :   if (!IsBswapLHS && !IsBswapRHS)
     118             :     return nullptr;
     119             : 
     120          12 :   if (!IsBswapLHS && !ConstLHS)
     121             :     return nullptr;
     122             : 
     123          12 :   if (!IsBswapRHS && !ConstRHS)
     124             :     return nullptr;
     125             : 
     126             :   /// OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) )
     127             :   /// OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) )
     128          12 :   Value *NewLHS = IsBswapLHS ? IntrLHS->getOperand(0) :
     129          12 :                   Builder->getInt(ConstLHS->getValue().byteSwap());
     130             : 
     131          18 :   Value *NewRHS = IsBswapRHS ? IntrRHS->getOperand(0) :
     132          18 :                   Builder->getInt(ConstRHS->getValue().byteSwap());
     133             : 
     134          24 :   Value *BinOp = Builder->CreateBinOp(I.getOpcode(), NewLHS, NewRHS);
     135          36 :   Function *F = Intrinsic::getDeclaration(I.getModule(), Intrinsic::bswap, ITy);
     136          24 :   return Builder->CreateCall(F, BinOp);
     137             : }
     138             : 
     139             : /// This handles expressions of the form ((val OP C1) & C2).  Where
     140             : /// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'.
     141        5777 : Instruction *InstCombiner::OptAndOp(BinaryOperator *Op,
     142             :                                     ConstantInt *OpRHS,
     143             :                                     ConstantInt *AndRHS,
     144             :                                     BinaryOperator &TheAnd) {
     145        5777 :   Value *X = Op->getOperand(0);
     146        5777 :   Constant *Together = nullptr;
     147       11554 :   if (!Op->isShift())
     148        2036 :     Together = ConstantExpr::getAnd(AndRHS, OpRHS);
     149             : 
     150        5777 :   switch (Op->getOpcode()) {
     151             :   default: break;
     152             :   case Instruction::Xor:
     153          18 :     if (Op->hasOneUse()) {
     154             :       // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
     155           4 :       Value *And = Builder->CreateAnd(X, AndRHS);
     156           4 :       And->takeName(Op);
     157           8 :       return BinaryOperator::CreateXor(And, Together);
     158             :     }
     159             :     break;
     160             :   case Instruction::Or:
     161          60 :     if (Op->hasOneUse()){
     162          18 :       ConstantInt *TogetherCI = dyn_cast<ConstantInt>(Together);
     163          36 :       if (TogetherCI && !TogetherCI->isZero()){
     164             :         // (X | C1) & C2 --> (X & (C2^(C1&C2))) | C1
     165             :         // NOTE: This reduces the number of bits set in the & mask, which
     166             :         // can expose opportunities for store narrowing.
     167          18 :         Together = ConstantExpr::getXor(AndRHS, Together);
     168          18 :         Value *And = Builder->CreateAnd(X, Together);
     169          18 :         And->takeName(Op);
     170          36 :         return BinaryOperator::CreateOr(And, OpRHS);
     171             :       }
     172             :     }
     173             : 
     174             :     break;
     175             :   case Instruction::Add:
     176        3948 :     if (Op->hasOneUse()) {
     177             :       // Adding a one to a single bit bit-field should be turned into an XOR
     178             :       // of the bit.  First thing to check is to see if this AND is with a
     179             :       // single bit constant.
     180         607 :       const APInt &AndRHSV = AndRHS->getValue();
     181             : 
     182             :       // If there is only one bit set.
     183         607 :       if (AndRHSV.isPowerOf2()) {
     184             :         // Ok, at this point, we know that we are masking the result of the
     185             :         // ADD down to exactly one bit.  If the constant we are adding has
     186             :         // no bits set below this bit, then we can eliminate the ADD.
     187          16 :         const APInt& AddRHS = OpRHS->getValue();
     188             : 
     189             :         // Check to see if any bits below the one bit set in AndRHSV are set.
     190          96 :         if ((AddRHS & (AndRHSV-1)) == 0) {
     191             :           // If not, the only thing that can effect the output of the AND is
     192             :           // the bit specified by AndRHSV.  If that bit is set, the effect of
     193             :           // the XOR is to toggle the bit.  If it is clear, then the ADD has
     194             :           // no effect.
     195          64 :           if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop
     196           0 :             TheAnd.setOperand(0, X);
     197           0 :             return &TheAnd;
     198             :           } else {
     199             :             // Pull the XOR out of the AND.
     200          16 :             Value *NewAnd = Builder->CreateAnd(X, AndRHS);
     201          16 :             NewAnd->takeName(Op);
     202          32 :             return BinaryOperator::CreateXor(NewAnd, AndRHS);
     203             :           }
     204             :         }
     205             :       }
     206             :     }
     207             :     break;
     208             : 
     209             :   case Instruction::Shl: {
     210             :     // We know that the AND will not produce any of the bits shifted in, so if
     211             :     // the anded constant includes them, clear them now!
     212             :     //
     213        1332 :     uint32_t BitWidth = AndRHS->getType()->getBitWidth();
     214        1332 :     uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
     215         666 :     APInt ShlMask(APInt::getHighBitsSet(BitWidth, BitWidth-OpRHSVal));
     216        3996 :     ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShlMask);
     217             : 
     218        1332 :     if (CI->getValue() == ShlMask)
     219             :       // Masking out bits that the shift already masks.
     220           0 :       return replaceInstUsesWith(TheAnd, Op);   // No need for the and.
     221             : 
     222         666 :     if (CI != AndRHS) {                  // Reducing bits set in and.
     223           0 :       TheAnd.setOperand(1, CI);
     224           0 :       return &TheAnd;
     225             :     }
     226         666 :     break;
     227             :   }
     228             :   case Instruction::LShr: {
     229             :     // We know that the AND will not produce any of the bits shifted in, so if
     230             :     // the anded constant includes them, clear them now!  This only applies to
     231             :     // unsigned shifts, because a signed shr may bring in set bits!
     232             :     //
     233        5864 :     uint32_t BitWidth = AndRHS->getType()->getBitWidth();
     234        5864 :     uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
     235        2932 :     APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal));
     236       17592 :     ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShrMask);
     237             : 
     238        5864 :     if (CI->getValue() == ShrMask)
     239             :       // Masking out bits that the shift already masks.
     240           0 :       return replaceInstUsesWith(TheAnd, Op);
     241             : 
     242        2932 :     if (CI != AndRHS) {
     243           0 :       TheAnd.setOperand(1, CI);  // Reduce bits set in and cst.
     244           0 :       return &TheAnd;
     245             :     }
     246        2932 :     break;
     247             :   }
     248             :   case Instruction::AShr:
     249             :     // Signed shr.
     250             :     // See if this is shifting in some sign extension, then masking it out
     251             :     // with an and.
     252         286 :     if (Op->hasOneUse()) {
     253          14 :       uint32_t BitWidth = AndRHS->getType()->getBitWidth();
     254          14 :       uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
     255          14 :       APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal));
     256          42 :       Constant *C = Builder->getInt(AndRHS->getValue() & ShrMask);
     257           7 :       if (C == AndRHS) {          // Masking out bits shifted in.
     258             :         // (Val ashr C1) & C2 -> (Val lshr C1) & C2
     259             :         // Make the argument unsigned.
     260           0 :         Value *ShVal = Op->getOperand(0);
     261           0 :         ShVal = Builder->CreateLShr(ShVal, OpRHS, Op->getName());
     262           0 :         return BinaryOperator::CreateAnd(ShVal, AndRHS, TheAnd.getName());
     263             :       }
     264             :     }
     265             :     break;
     266             :   }
     267             :   return nullptr;
     268             : }
     269             : 
     270             : /// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise
     271             : /// (V < Lo || V >= Hi). This method expects that Lo <= Hi. IsSigned indicates
     272             : /// whether to treat V, Lo, and Hi as signed or not.
     273          60 : Value *InstCombiner::insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
     274             :                                      bool isSigned, bool Inside) {
     275             :   assert((isSigned ? Lo.sle(Hi) : Lo.ule(Hi)) &&
     276             :          "Lo is not <= Hi in range emission code!");
     277             : 
     278          60 :   Type *Ty = V->getType();
     279          60 :   if (Lo == Hi)
     280           0 :     return Inside ? ConstantInt::getFalse(Ty) : ConstantInt::getTrue(Ty);
     281             : 
     282             :   // V >= Min && V <  Hi --> V <  Hi
     283             :   // V <  Min || V >= Hi --> V >= Hi
     284          60 :   ICmpInst::Predicate Pred = Inside ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE;
     285          69 :   if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) {
     286           5 :     Pred = isSigned ? ICmpInst::getSignedPredicate(Pred) : Pred;
     287           5 :     return Builder->CreateICmp(Pred, V, ConstantInt::get(Ty, Hi));
     288             :   }
     289             : 
     290             :   // V >= Lo && V <  Hi --> V - Lo u<  Hi - Lo
     291             :   // V <  Lo || V >= Hi --> V - Lo u>= Hi - Lo
     292             :   Value *VMinusLo =
     293         110 :       Builder->CreateSub(V, ConstantInt::get(Ty, Lo), V->getName() + ".off");
     294         220 :   Constant *HiMinusLo = ConstantInt::get(Ty, Hi - Lo);
     295          55 :   return Builder->CreateICmp(Pred, VMinusLo, HiMinusLo);
     296             : }
     297             : 
     298             : /// Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns
     299             : /// that can be simplified.
     300             : /// One of A and B is considered the mask. The other is the value. This is
     301             : /// described as the "AMask" or "BMask" part of the enum. If the enum contains
     302             : /// only "Mask", then both A and B can be considered masks. If A is the mask,
     303             : /// then it was proven that (A & C) == C. This is trivial if C == A or C == 0.
     304             : /// If both A and C are constants, this proof is also easy.
     305             : /// For the following explanations, we assume that A is the mask.
     306             : ///
     307             : /// "AllOnes" declares that the comparison is true only if (A & B) == A or all
     308             : /// bits of A are set in B.
     309             : ///   Example: (icmp eq (A & 3), 3) -> AMask_AllOnes
     310             : ///
     311             : /// "AllZeros" declares that the comparison is true only if (A & B) == 0 or all
     312             : /// bits of A are cleared in B.
     313             : ///   Example: (icmp eq (A & 3), 0) -> Mask_AllZeroes
     314             : ///
     315             : /// "Mixed" declares that (A & B) == C and C might or might not contain any
     316             : /// number of one bits and zero bits.
     317             : ///   Example: (icmp eq (A & 3), 1) -> AMask_Mixed
     318             : ///
     319             : /// "Not" means that in above descriptions "==" should be replaced by "!=".
     320             : ///   Example: (icmp ne (A & 3), 3) -> AMask_NotAllOnes
     321             : ///
     322             : /// If the mask A contains a single bit, then the following is equivalent:
     323             : ///    (icmp eq (A & B), A) equals (icmp ne (A & B), 0)
     324             : ///    (icmp ne (A & B), A) equals (icmp eq (A & B), 0)
     325             : enum MaskedICmpType {
     326             :   AMask_AllOnes           =     1,
     327             :   AMask_NotAllOnes        =     2,
     328             :   BMask_AllOnes           =     4,
     329             :   BMask_NotAllOnes        =     8,
     330             :   Mask_AllZeros           =    16,
     331             :   Mask_NotAllZeros        =    32,
     332             :   AMask_Mixed             =    64,
     333             :   AMask_NotMixed          =   128,
     334             :   BMask_Mixed             =   256,
     335             :   BMask_NotMixed          =   512
     336             : };
     337             : 
     338             : /// Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C)
     339             : /// satisfies.
     340         802 : static unsigned getMaskedICmpType(Value *A, Value *B, Value *C,
     341             :                                   ICmpInst::Predicate Pred) {
     342         802 :   ConstantInt *ACst = dyn_cast<ConstantInt>(A);
     343         802 :   ConstantInt *BCst = dyn_cast<ConstantInt>(B);
     344         802 :   ConstantInt *CCst = dyn_cast<ConstantInt>(C);
     345         802 :   bool IsEq = (Pred == ICmpInst::ICMP_EQ);
     346        1416 :   bool IsAPow2 = (ACst && !ACst->isZero() && ACst->getValue().isPowerOf2());
     347        1025 :   bool IsBPow2 = (BCst && !BCst->isZero() && BCst->getValue().isPowerOf2());
     348         802 :   unsigned MaskVal = 0;
     349        1426 :   if (CCst && CCst->isZero()) {
     350             :     // if C is zero, then both A and B qualify as mask
     351         355 :     MaskVal |= (IsEq ? (Mask_AllZeros | AMask_Mixed | BMask_Mixed)
     352             :                      : (Mask_NotAllZeros | AMask_NotMixed | BMask_NotMixed));
     353         355 :     if (IsAPow2)
     354           8 :       MaskVal |= (IsEq ? (AMask_NotAllOnes | AMask_NotMixed)
     355             :                        : (AMask_AllOnes | AMask_Mixed));
     356         355 :     if (IsBPow2)
     357          25 :       MaskVal |= (IsEq ? (BMask_NotAllOnes | BMask_NotMixed)
     358             :                        : (BMask_AllOnes | BMask_Mixed));
     359             :     return MaskVal;
     360             :   }
     361             : 
     362         447 :   if (A == C) {
     363         116 :     MaskVal |= (IsEq ? (AMask_AllOnes | AMask_Mixed)
     364             :                      : (AMask_NotAllOnes | AMask_NotMixed));
     365         116 :     if (IsAPow2)
     366           0 :       MaskVal |= (IsEq ? (Mask_NotAllZeros | AMask_NotMixed)
     367             :                        : (Mask_AllZeros | AMask_Mixed));
     368         331 :   } else if (ACst && CCst && ConstantExpr::getAnd(ACst, CCst) == CCst) {
     369          86 :     MaskVal |= (IsEq ? AMask_Mixed : AMask_NotMixed);
     370             :   }
     371             : 
     372         447 :   if (B == C) {
     373          30 :     MaskVal |= (IsEq ? (BMask_AllOnes | BMask_Mixed)
     374             :                      : (BMask_NotAllOnes | BMask_NotMixed));
     375          30 :     if (IsBPow2)
     376           0 :       MaskVal |= (IsEq ? (Mask_NotAllZeros | BMask_NotMixed)
     377             :                        : (Mask_AllZeros | BMask_Mixed));
     378         417 :   } else if (BCst && CCst && ConstantExpr::getAnd(BCst, CCst) == CCst) {
     379          63 :     MaskVal |= (IsEq ? BMask_Mixed : BMask_NotMixed);
     380             :   }
     381             : 
     382             :   return MaskVal;
     383             : }
     384             : 
     385             : /// Convert an analysis of a masked ICmp into its equivalent if all boolean
     386             : /// operations had the opposite sense. Since each "NotXXX" flag (recording !=)
     387             : /// is adjacent to the corresponding normal flag (recording ==), this just
     388             : /// involves swapping those bits over.
     389             : static unsigned conjugateICmpMask(unsigned Mask) {
     390             :   unsigned NewMask;
     391         111 :   NewMask = (Mask & (AMask_AllOnes | BMask_AllOnes | Mask_AllZeros |
     392             :                      AMask_Mixed | BMask_Mixed))
     393         111 :             << 1;
     394             : 
     395         111 :   NewMask |= (Mask & (AMask_NotAllOnes | BMask_NotAllOnes | Mask_NotAllZeros |
     396             :                       AMask_NotMixed | BMask_NotMixed))
     397         111 :              >> 1;
     398             : 
     399             :   return NewMask;
     400             : }
     401             : 
     402             : /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
     403             : /// Return the set of pattern classes (from MaskedICmpType) that both LHS and
     404             : /// RHS satisfy.
     405        3424 : static unsigned getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C,
     406             :                                          Value *&D, Value *&E, ICmpInst *LHS,
     407             :                                          ICmpInst *RHS,
     408             :                                          ICmpInst::Predicate &PredL,
     409             :                                          ICmpInst::Predicate &PredR) {
     410       10272 :   if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType())
     411             :     return 0;
     412             :   // vectors are not (yet?) supported
     413        6507 :   if (LHS->getOperand(0)->getType()->isVectorTy())
     414             :     return 0;
     415             : 
     416             :   // Here comes the tricky part:
     417             :   // LHS might be of the form L11 & L12 == X, X == L21 & L22,
     418             :   // and L11 & L12 == L21 & L22. The same goes for RHS.
     419             :   // Now we must find those components L** and R**, that are equal, so
     420             :   // that we can extract the parameters A, B, C, D, and E for the canonical
     421             :   // above.
     422        4308 :   Value *L1 = LHS->getOperand(0);
     423        4308 :   Value *L2 = LHS->getOperand(1);
     424             :   Value *L11, *L12, *L21, *L22;
     425             :   // Check whether the icmp can be decomposed into a bit test.
     426        2154 :   if (decomposeBitTestICmp(LHS, PredL, L11, L12, L2)) {
     427          48 :     L21 = L22 = L1 = nullptr;
     428             :   } else {
     429             :     // Look for ANDs in the LHS icmp.
     430        4212 :     if (!L1->getType()->isIntegerTy()) {
     431             :       // You can icmp pointers, for example. They really aren't masks.
     432         892 :       L11 = L12 = nullptr;
     433        4856 :     } else if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) {
     434             :       // Any icmp can be viewed as being trivially masked; if it allows us to
     435             :       // remove one, it's worth it.
     436        1081 :       L11 = L1;
     437        1081 :       L12 = Constant::getAllOnesValue(L1->getType());
     438             :     }
     439             : 
     440        4212 :     if (!L2->getType()->isIntegerTy()) {
     441             :       // You can icmp pointers, for example. They really aren't masks.
     442         892 :       L21 = L22 = nullptr;
     443        4856 :     } else if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) {
     444        1210 :       L21 = L2;
     445        1210 :       L22 = Constant::getAllOnesValue(L2->getType());
     446             :     }
     447             :   }
     448             : 
     449             :   // Bail if LHS was a icmp that can't be decomposed into an equality.
     450        4308 :   if (!ICmpInst::isEquality(PredL))
     451             :     return 0;
     452             : 
     453        2184 :   Value *R1 = RHS->getOperand(0);
     454        2184 :   Value *R2 = RHS->getOperand(1);
     455             :   Value *R11, *R12;
     456        1092 :   bool Ok = false;
     457        1092 :   if (decomposeBitTestICmp(RHS, PredR, R11, R12, R2)) {
     458          31 :     if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
     459          13 :       A = R11;
     460          13 :       D = R12;
     461          18 :     } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
     462           6 :       A = R12;
     463           6 :       D = R11;
     464             :     } else {
     465             :       return 0;
     466             :     }
     467          19 :     E = R2;
     468          19 :     R1 = nullptr;
     469          19 :     Ok = true;
     470        2122 :   } else if (R1->getType()->isIntegerTy()) {
     471        1712 :     if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) {
     472             :       // As before, model no mask as a trivial mask if it'll let us do an
     473             :       // optimization.
     474         360 :       R11 = R1;
     475         360 :       R12 = Constant::getAllOnesValue(R1->getType());
     476             :     }
     477             : 
     478         428 :     if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
     479          83 :       A = R11;
     480          83 :       D = R12;
     481          83 :       E = R2;
     482          83 :       Ok = true;
     483         345 :     } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
     484         316 :       A = R12;
     485         316 :       D = R11;
     486         316 :       E = R2;
     487         316 :       Ok = true;
     488             :     }
     489             :   }
     490             : 
     491             :   // Bail if RHS was a icmp that can't be decomposed into an equality.
     492        2160 :   if (!ICmpInst::isEquality(PredR))
     493             :     return 0;
     494             : 
     495             :   // Look for ANDs on the right side of the RHS icmp.
     496        1713 :   if (!Ok && R2->getType()->isIntegerTy()) {
     497          96 :     if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) {
     498          22 :       R11 = R2;
     499          22 :       R12 = Constant::getAllOnesValue(R2->getType());
     500             :     }
     501             : 
     502          24 :     if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
     503           0 :       A = R11;
     504           0 :       D = R12;
     505           0 :       E = R1;
     506           0 :       Ok = true;
     507          24 :     } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
     508           2 :       A = R12;
     509           2 :       D = R11;
     510           2 :       E = R1;
     511           2 :       Ok = true;
     512             :     } else {
     513             :       return 0;
     514             :     }
     515             :   }
     516        1034 :   if (!Ok)
     517             :     return 0;
     518             : 
     519         401 :   if (L11 == A) {
     520          86 :     B = L12;
     521          86 :     C = L2;
     522         315 :   } else if (L12 == A) {
     523         236 :     B = L11;
     524         236 :     C = L2;
     525          79 :   } else if (L21 == A) {
     526           2 :     B = L22;
     527           2 :     C = L1;
     528          77 :   } else if (L22 == A) {
     529          77 :     B = L21;
     530          77 :     C = L1;
     531             :   }
     532             : 
     533         401 :   unsigned LeftType = getMaskedICmpType(A, B, C, PredL);
     534         401 :   unsigned RightType = getMaskedICmpType(A, D, E, PredR);
     535         401 :   return LeftType & RightType;
     536             : }
     537             : 
     538             : /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
     539             : /// into a single (icmp(A & X) ==/!= Y).
     540        3424 : static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
     541             :                                      llvm::InstCombiner::BuilderTy *Builder) {
     542        3424 :   Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
     543       10272 :   ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
     544             :   unsigned Mask =
     545        3424 :       getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
     546        3424 :   if (Mask == 0)
     547             :     return nullptr;
     548             : 
     549             :   assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) &&
     550             :          "Expected equality predicates for masked type of icmps.");
     551             : 
     552             :   // In full generality:
     553             :   //     (icmp (A & B) Op C) | (icmp (A & D) Op E)
     554             :   // ==  ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ]
     555             :   //
     556             :   // If the latter can be converted into (icmp (A & X) Op Y) then the former is
     557             :   // equivalent to (icmp (A & X) !Op Y).
     558             :   //
     559             :   // Therefore, we can pretend for the rest of this function that we're dealing
     560             :   // with the conjunction, provided we flip the sense of any comparisons (both
     561             :   // input and output).
     562             : 
     563             :   // In most cases we're going to produce an EQ for the "&&" case.
     564         181 :   ICmpInst::Predicate NewCC = IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
     565         181 :   if (!IsAnd) {
     566             :     // Convert the masking analysis into its equivalent with negated
     567             :     // comparisons.
     568         111 :     Mask = conjugateICmpMask(Mask);
     569             :   }
     570             : 
     571         181 :   if (Mask & Mask_AllZeros) {
     572             :     // (icmp eq (A & B), 0) & (icmp eq (A & D), 0)
     573             :     // -> (icmp eq (A & (B|D)), 0)
     574          25 :     Value *NewOr = Builder->CreateOr(B, D);
     575          25 :     Value *NewAnd = Builder->CreateAnd(A, NewOr);
     576             :     // We can't use C as zero because we might actually handle
     577             :     //   (icmp ne (A & B), B) & (icmp ne (A & D), D)
     578             :     // with B and D, having a single bit set.
     579          25 :     Value *Zero = Constant::getNullValue(A->getType());
     580          25 :     return Builder->CreateICmp(NewCC, NewAnd, Zero);
     581             :   }
     582         156 :   if (Mask & BMask_AllOnes) {
     583             :     // (icmp eq (A & B), B) & (icmp eq (A & D), D)
     584             :     // -> (icmp eq (A & (B|D)), (B|D))
     585          14 :     Value *NewOr = Builder->CreateOr(B, D);
     586          14 :     Value *NewAnd = Builder->CreateAnd(A, NewOr);
     587          14 :     return Builder->CreateICmp(NewCC, NewAnd, NewOr);
     588             :   }
     589         142 :   if (Mask & AMask_AllOnes) {
     590             :     // (icmp eq (A & B), A) & (icmp eq (A & D), A)
     591             :     // -> (icmp eq (A & (B&D)), A)
     592           8 :     Value *NewAnd1 = Builder->CreateAnd(B, D);
     593           8 :     Value *NewAnd2 = Builder->CreateAnd(A, NewAnd1);
     594           8 :     return Builder->CreateICmp(NewCC, NewAnd2, A);
     595             :   }
     596             : 
     597             :   // Remaining cases assume at least that B and D are constant, and depend on
     598             :   // their actual values. This isn't strictly necessary, just a "handle the
     599             :   // easy cases for now" decision.
     600         268 :   ConstantInt *BCst = dyn_cast<ConstantInt>(B);
     601         134 :   if (!BCst)
     602             :     return nullptr;
     603          96 :   ConstantInt *DCst = dyn_cast<ConstantInt>(D);
     604          48 :   if (!DCst)
     605             :     return nullptr;
     606             : 
     607          48 :   if (Mask & (Mask_NotAllZeros | BMask_NotAllOnes)) {
     608             :     // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and
     609             :     // (icmp ne (A & B), B) & (icmp ne (A & D), D)
     610             :     //     -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0)
     611             :     // Only valid if one of the masks is a superset of the other (check "B&D" is
     612             :     // the same as either B or D).
     613          36 :     APInt NewMask = BCst->getValue() & DCst->getValue();
     614             : 
     615          14 :     if (NewMask == BCst->getValue())
     616           6 :       return LHS;
     617           4 :     else if (NewMask == DCst->getValue())
     618             :       return RHS;
     619             :   }
     620             : 
     621          42 :   if (Mask & AMask_NotAllOnes) {
     622             :     // (icmp ne (A & B), B) & (icmp ne (A & D), D)
     623             :     //     -> (icmp ne (A & B), A) or (icmp ne (A & D), A)
     624             :     // Only valid if one of the masks is a superset of the other (check "B|D" is
     625             :     // the same as either B or D).
     626          10 :     APInt NewMask = BCst->getValue() | DCst->getValue();
     627             : 
     628           4 :     if (NewMask == BCst->getValue())
     629           2 :       return LHS;
     630           4 :     else if (NewMask == DCst->getValue())
     631             :       return RHS;
     632             :   }
     633             : 
     634          40 :   if (Mask & BMask_Mixed) {
     635             :     // (icmp eq (A & B), C) & (icmp eq (A & D), E)
     636             :     // We already know that B & C == C && D & E == E.
     637             :     // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
     638             :     // C and E, which are shared by both the mask B and the mask D, don't
     639             :     // contradict, then we can transform to
     640             :     // -> (icmp eq (A & (B|D)), (C|E))
     641             :     // Currently, we only handle the case of B, C, D, and E being constant.
     642             :     // We can't simply use C and E because we might actually handle
     643             :     //   (icmp ne (A & B), B) & (icmp eq (A & D), D)
     644             :     // with B and D, having a single bit set.
     645          16 :     ConstantInt *CCst = dyn_cast<ConstantInt>(C);
     646           8 :     if (!CCst)
     647             :       return nullptr;
     648          16 :     ConstantInt *ECst = dyn_cast<ConstantInt>(E);
     649           8 :     if (!ECst)
     650             :       return nullptr;
     651           8 :     if (PredL != NewCC)
     652           2 :       CCst = cast<ConstantInt>(ConstantExpr::getXor(BCst, CCst));
     653           8 :     if (PredR != NewCC)
     654           4 :       ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
     655             : 
     656             :     // If there is a conflict, we should actually return a false for the
     657             :     // whole construct.
     658          80 :     if (((BCst->getValue() & DCst->getValue()) &
     659          48 :          (CCst->getValue() ^ ECst->getValue())) != 0)
     660           2 :       return ConstantInt::get(LHS->getType(), !IsAnd);
     661             : 
     662           6 :     Value *NewOr1 = Builder->CreateOr(B, D);
     663           6 :     Value *NewOr2 = ConstantExpr::getOr(CCst, ECst);
     664           6 :     Value *NewAnd = Builder->CreateAnd(A, NewOr1);
     665           6 :     return Builder->CreateICmp(NewCC, NewAnd, NewOr2);
     666             :   }
     667             : 
     668             :   return nullptr;
     669             : }
     670             : 
     671             : /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
     672             : /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
     673             : /// If \p Inverted is true then the check is for the inverted range, e.g.
     674             : /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
     675        6708 : Value *InstCombiner::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1,
     676             :                                         bool Inverted) {
     677             :   // Check the lower range comparison, e.g. x >= 0
     678             :   // InstCombine already ensured that if there is a constant it's on the RHS.
     679       20124 :   ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
     680        6708 :   if (!RangeStart)
     681             :     return nullptr;
     682             : 
     683        5298 :   ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
     684        3468 :                                Cmp0->getPredicate());
     685             : 
     686             :   // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
     687        5343 :   if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
     688          34 :         (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
     689             :     return nullptr;
     690             : 
     691          72 :   ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
     692          48 :                                Cmp1->getPredicate());
     693             : 
     694          72 :   Value *Input = Cmp0->getOperand(0);
     695             :   Value *RangeEnd;
     696          72 :   if (Cmp1->getOperand(0) == Input) {
     697             :     // For the upper range compare we have: icmp x, n
     698           4 :     RangeEnd = Cmp1->getOperand(1);
     699          64 :   } else if (Cmp1->getOperand(1) == Input) {
     700             :     // For the upper range compare we have: icmp n, x
     701          20 :     RangeEnd = Cmp1->getOperand(0);
     702          10 :     Pred1 = ICmpInst::getSwappedPredicate(Pred1);
     703             :   } else {
     704             :     return nullptr;
     705             :   }
     706             : 
     707             :   // Check the upper range comparison, e.g. x < n
     708             :   ICmpInst::Predicate NewPred;
     709          14 :   switch (Pred1) {
     710             :     case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
     711           4 :     case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
     712             :     default: return nullptr;
     713             :   }
     714             : 
     715             :   // This simplification is only valid if the upper range is not negative.
     716             :   bool IsNegative, IsNotNegative;
     717          11 :   ComputeSignBit(RangeEnd, IsNotNegative, IsNegative, /*Depth=*/0, Cmp1);
     718          11 :   if (!IsNotNegative)
     719             :     return nullptr;
     720             : 
     721           9 :   if (Inverted)
     722           4 :     NewPred = ICmpInst::getInversePredicate(NewPred);
     723             : 
     724           9 :   return Builder->CreateICmp(NewPred, Input, RangeEnd);
     725             : }
     726             : 
     727             : static Value *
     728        3347 : foldAndOrOfEqualityCmpsWithConstants(ICmpInst *LHS, ICmpInst *RHS,
     729             :                                      bool JoinedByAnd,
     730             :                                      InstCombiner::BuilderTy *Builder) {
     731        6694 :   Value *X = LHS->getOperand(0);
     732        6694 :   if (X != RHS->getOperand(0))
     733             :     return nullptr;
     734             : 
     735             :   const APInt *C1, *C2;
     736        4103 :   if (!match(LHS->getOperand(1), m_APInt(C1)) ||
     737         201 :       !match(RHS->getOperand(1), m_APInt(C2)))
     738             :     return nullptr;
     739             : 
     740             :   // We only handle (X != C1 && X != C2) and (X == C1 || X == C2).
     741         124 :   ICmpInst::Predicate Pred = LHS->getPredicate();
     742         124 :   if (Pred !=  RHS->getPredicate())
     743             :     return nullptr;
     744          32 :   if (JoinedByAnd && Pred != ICmpInst::ICMP_NE)
     745             :     return nullptr;
     746          32 :   if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ)
     747             :     return nullptr;
     748             : 
     749             :   // The larger unsigned constant goes on the right.
     750          64 :   if (C1->ugt(*C2))
     751             :     std::swap(C1, C2);
     752             : 
     753         128 :   APInt Xor = *C1 ^ *C2;
     754          32 :   if (Xor.isPowerOf2()) {
     755             :     // If LHSC and RHSC differ by only one bit, then set that bit in X and
     756             :     // compare against the larger constant:
     757             :     // (X == C1 || X == C2) --> (X | (C1 ^ C2)) == C2
     758             :     // (X != C1 && X != C2) --> (X | (C1 ^ C2)) != C2
     759             :     // We choose an 'or' with a Pow2 constant rather than the inverse mask with
     760             :     // 'and' because that may lead to smaller codegen from a smaller constant.
     761          14 :     Value *Or = Builder->CreateOr(X, ConstantInt::get(X->getType(), Xor));
     762          14 :     return Builder->CreateICmp(Pred, Or, ConstantInt::get(X->getType(), *C2));
     763             :   }
     764             : 
     765             :   // Special case: get the ordering right when the values wrap around zero.
     766             :   // Ie, we assumed the constants were unsigned when swapping earlier.
     767          21 :   if (*C1 == 0 && C2->isAllOnesValue())
     768             :     std::swap(C1, C2);
     769             : 
     770         108 :   if (*C1 == *C2 - 1) {
     771             :     // (X == 13 || X == 14) --> X - 13 <=u 1
     772             :     // (X != 13 && X != 14) --> X - 13  >u 1
     773             :     // An 'add' is the canonical IR form, so favor that over a 'sub'.
     774          75 :     Value *Add = Builder->CreateAdd(X, ConstantInt::get(X->getType(), -(*C1)));
     775          15 :     auto NewPred = JoinedByAnd ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_ULE;
     776          15 :     return Builder->CreateICmp(NewPred, Add, ConstantInt::get(X->getType(), 1));
     777             :   }
     778             : 
     779             :   return nullptr;
     780             : }
     781             : 
     782             : /// Fold (icmp)&(icmp) if possible.
     783        1198 : Value *InstCombiner::FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
     784        3594 :   ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
     785             : 
     786             :   // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
     787        1198 :   if (PredicatesFoldable(PredL, PredR)) {
     788        3596 :     if (LHS->getOperand(0) == RHS->getOperand(1) &&
     789           6 :         LHS->getOperand(1) == RHS->getOperand(0))
     790           0 :       LHS->swapOperands();
     791        3700 :     if (LHS->getOperand(0) == RHS->getOperand(0) &&
     792         318 :         LHS->getOperand(1) == RHS->getOperand(1)) {
     793           0 :       Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
     794           0 :       unsigned Code = getICmpCode(LHS) & getICmpCode(RHS);
     795           0 :       bool isSigned = LHS->isSigned() || RHS->isSigned();
     796           0 :       return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
     797             :     }
     798             :   }
     799             : 
     800             :   // handle (roughly):  (icmp eq (A & B), C) & (icmp eq (A & D), E)
     801        1198 :   if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
     802             :     return V;
     803             : 
     804             :   // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
     805        1161 :   if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
     806             :     return V;
     807             : 
     808             :   // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
     809        1159 :   if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
     810             :     return V;
     811             : 
     812        1156 :   if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
     813             :     return V;
     814             : 
     815             :   // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
     816        3432 :   Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
     817        3432 :   ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
     818        3432 :   ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
     819        1144 :   if (!LHSC || !RHSC)
     820             :     return nullptr;
     821             : 
     822         292 :   if (LHSC == RHSC && PredL == PredR) {
     823             :     // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
     824             :     // where C is a power of 2 or
     825             :     // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
     826         330 :     if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) ||
     827           0 :         (PredL == ICmpInst::ICMP_EQ && LHSC->isZero())) {
     828           0 :       Value *NewOr = Builder->CreateOr(LHS0, RHS0);
     829           0 :       return Builder->CreateICmp(PredL, NewOr, LHSC);
     830             :     }
     831             :   }
     832             : 
     833             :   // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
     834             :   // where CMAX is the all ones value for the truncated type,
     835             :   // iff the lower bits of C2 and CA are zero.
     836         296 :   if (PredL == ICmpInst::ICMP_EQ && PredL == PredR && LHS->hasOneUse() &&
     837           4 :       RHS->hasOneUse()) {
     838             :     Value *V;
     839           2 :     ConstantInt *AndC, *SmallC = nullptr, *BigC = nullptr;
     840             : 
     841             :     // (trunc x) == C1 & (and x, CA) == C2
     842             :     // (and x, CA) == C2 & (trunc x) == C1
     843          10 :     if (match(RHS0, m_Trunc(m_Value(V))) &&
     844           4 :         match(LHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
     845             :       SmallC = RHSC;
     846             :       BigC = LHSC;
     847           6 :     } else if (match(LHS0, m_Trunc(m_Value(V))) &&
     848           4 :                match(RHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
     849           1 :       SmallC = LHSC;
     850           1 :       BigC = RHSC;
     851             :     }
     852             : 
     853           2 :     if (SmallC && BigC) {
     854           4 :       unsigned BigBitSize = BigC->getType()->getBitWidth();
     855           4 :       unsigned SmallBitSize = SmallC->getType()->getBitWidth();
     856             : 
     857             :       // Check that the low bits are zero.
     858           2 :       APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
     859          22 :       if ((Low & AndC->getValue()) == 0 && (Low & BigC->getValue()) == 0) {
     860          12 :         Value *NewAnd = Builder->CreateAnd(V, Low | AndC->getValue());
     861          10 :         APInt N = SmallC->getValue().zext(BigBitSize) | BigC->getValue();
     862           4 :         Value *NewVal = ConstantInt::get(AndC->getType()->getContext(), N);
     863           2 :         return Builder->CreateICmp(PredL, NewAnd, NewVal);
     864             :       }
     865             :     }
     866             :   }
     867             : 
     868             :   // From here on, we only handle:
     869             :   //    (icmp1 A, C1) & (icmp2 A, C2) --> something simpler.
     870         290 :   if (LHS0 != RHS0)
     871             :     return nullptr;
     872             : 
     873             :   // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
     874          12 :   if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
     875          12 :       PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
     876          12 :       PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
     877          12 :       PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
     878             :     return nullptr;
     879             : 
     880             :   // We can't fold (ugt x, C) & (sgt x, C2).
     881          12 :   if (!PredicatesFoldable(PredL, PredR))
     882             :     return nullptr;
     883             : 
     884             :   // Ensure that the larger constant is on the RHS.
     885             :   bool ShouldSwap;
     886          27 :   if (CmpInst::isSigned(PredL) ||
     887           8 :       (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
     888          40 :     ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
     889             :   else
     890           8 :     ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
     891             : 
     892          12 :   if (ShouldSwap) {
     893           1 :     std::swap(LHS, RHS);
     894           1 :     std::swap(LHSC, RHSC);
     895             :     std::swap(PredL, PredR);
     896             :   }
     897             : 
     898             :   // At this point, we know we have two icmp instructions
     899             :   // comparing a value against two constants and and'ing the result
     900             :   // together.  Because of the above check, we know that we only have
     901             :   // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know
     902             :   // (from the icmp folding check above), that the two constants
     903             :   // are not equal and that the larger constant is on the RHS
     904             :   assert(LHSC != RHSC && "Compares not folded above?");
     905             : 
     906          12 :   switch (PredL) {
     907             :   default:
     908           0 :     llvm_unreachable("Unknown integer condition code!");
     909             :   case ICmpInst::ICMP_NE:
     910           1 :     switch (PredR) {
     911             :     default:
     912           0 :       llvm_unreachable("Unknown integer condition code!");
     913             :     case ICmpInst::ICMP_ULT:
     914           1 :       if (LHSC == SubOne(RHSC)) // (X != 13 & X u< 14) -> X < 13
     915           0 :         return Builder->CreateICmpULT(LHS0, LHSC);
     916           1 :       if (LHSC->isNullValue()) // (X !=  0 & X u< 14) -> X-1 u< 13
     917           7 :         return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
     918           1 :                                false, true);
     919             :       break; // (X != 13 & X u< 15) -> no change
     920             :     case ICmpInst::ICMP_SLT:
     921           0 :       if (LHSC == SubOne(RHSC)) // (X != 13 & X s< 14) -> X < 13
     922           0 :         return Builder->CreateICmpSLT(LHS0, LHSC);
     923             :       break;                 // (X != 13 & X s< 15) -> no change
     924             :     case ICmpInst::ICMP_NE:
     925             :       // Potential folds for this case should already be handled.
     926             :       break;
     927             :     }
     928             :     break;
     929             :   case ICmpInst::ICMP_UGT:
     930           1 :     switch (PredR) {
     931             :     default:
     932           0 :       llvm_unreachable("Unknown integer condition code!");
     933             :     case ICmpInst::ICMP_NE:
     934           0 :       if (RHSC == AddOne(LHSC)) // (X u> 13 & X != 14) -> X u> 14
     935           0 :         return Builder->CreateICmp(PredL, LHS0, RHSC);
     936             :       break;                 // (X u> 13 & X != 15) -> no change
     937             :     case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1
     938           7 :       return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
     939           1 :                              false, true);
     940             :     }
     941             :     break;
     942             :   case ICmpInst::ICMP_SGT:
     943          10 :     switch (PredR) {
     944             :     default:
     945           0 :       llvm_unreachable("Unknown integer condition code!");
     946             :     case ICmpInst::ICMP_NE:
     947           2 :       if (RHSC == AddOne(LHSC)) // (X s> 13 & X != 14) -> X s> 14
     948           1 :         return Builder->CreateICmp(PredL, LHS0, RHSC);
     949             :       break;                 // (X s> 13 & X != 15) -> no change
     950             :     case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1
     951          56 :       return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true,
     952           8 :                              true);
     953             :     }
     954             :     break;
     955             :   }
     956             : 
     957             :   return nullptr;
     958             : }
     959             : 
     960             : /// Optimize (fcmp)&(fcmp).  NOTE: Unlike the rest of instcombine, this returns
     961             : /// a Value which should already be inserted into the function.
     962         487 : Value *InstCombiner::FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
     963        1461 :   Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1);
     964        1461 :   Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1);
     965        1461 :   FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate();
     966             : 
     967         487 :   if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) {
     968             :     // Swap RHS operands to match LHS.
     969           0 :     Op1CC = FCmpInst::getSwappedPredicate(Op1CC);
     970             :     std::swap(Op1LHS, Op1RHS);
     971             :   }
     972             : 
     973             :   // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
     974             :   // Suppose the relation between x and y is R, where R is one of
     975             :   // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
     976             :   // testing the desired relations.
     977             :   //
     978             :   // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
     979             :   //    bool(R & CC0) && bool(R & CC1)
     980             :   //  = bool((R & CC0) & (R & CC1))
     981             :   //  = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
     982         487 :   if (Op0LHS == Op1LHS && Op0RHS == Op1RHS)
     983         105 :     return getFCmpValue(getFCmpCode(Op0CC) & getFCmpCode(Op1CC), Op0LHS, Op0RHS,
     984         105 :                         Builder);
     985             : 
     986         768 :   if (LHS->getPredicate() == FCmpInst::FCMP_ORD &&
     987           8 :       RHS->getPredicate() == FCmpInst::FCMP_ORD) {
     988          12 :     if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType())
     989             :       return nullptr;
     990             : 
     991             :     // (fcmp ord x, c) & (fcmp ord y, c)  -> (fcmp ord x, y)
     992           6 :     if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1)))
     993           3 :       if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) {
     994             :         // If either of the constants are nans, then the whole thing returns
     995             :         // false.
     996           3 :         if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN())
     997           0 :           return Builder->getFalse();
     998           4 :         return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0));
     999             :       }
    1000             : 
    1001             :     // Handle vector zeros.  This occurs because the canonical form of
    1002             :     // "fcmp ord x,x" is "fcmp ord x, 0".
    1003           4 :     if (isa<ConstantAggregateZero>(LHS->getOperand(1)) &&
    1004           2 :         isa<ConstantAggregateZero>(RHS->getOperand(1)))
    1005           4 :       return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0));
    1006             :     return nullptr;
    1007             :   }
    1008             : 
    1009             :   return nullptr;
    1010             : }
    1011             : 
    1012             : /// Match De Morgan's Laws:
    1013             : /// (~A & ~B) == (~(A | B))
    1014             : /// (~A | ~B) == (~(A & B))
    1015       60491 : static Instruction *matchDeMorgansLaws(BinaryOperator &I,
    1016             :                                        InstCombiner::BuilderTy *Builder) {
    1017       60491 :   auto Opcode = I.getOpcode();
    1018             :   assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
    1019             :          "Trying to match De Morgan's Laws with something other than and/or");
    1020             :   // Flip the logic operation.
    1021       60491 :   if (Opcode == Instruction::And)
    1022             :     Opcode = Instruction::Or;
    1023             :   else
    1024       23026 :     Opcode = Instruction::And;
    1025             : 
    1026       60491 :   Value *Op0 = I.getOperand(0);
    1027       60491 :   Value *Op1 = I.getOperand(1);
    1028             :   // TODO: Use pattern matchers instead of dyn_cast.
    1029       60491 :   if (Value *Op0NotVal = dyn_castNotVal(Op0))
    1030         785 :     if (Value *Op1NotVal = dyn_castNotVal(Op1))
    1031          36 :       if (Op0->hasOneUse() && Op1->hasOneUse()) {
    1032             :         Value *LogicOp = Builder->CreateBinOp(Opcode, Op0NotVal, Op1NotVal,
    1033          34 :                                               I.getName() + ".demorgan");
    1034          17 :         return BinaryOperator::CreateNot(LogicOp);
    1035             :       }
    1036             : 
    1037             :   return nullptr;
    1038             : }
    1039             : 
    1040         168 : bool InstCombiner::shouldOptimizeCast(CastInst *CI) {
    1041         336 :   Value *CastSrc = CI->getOperand(0);
    1042             : 
    1043             :   // Noop casts and casts of constants should be eliminated trivially.
    1044         504 :   if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
    1045             :     return false;
    1046             : 
    1047             :   // If this cast is paired with another cast that can be eliminated, we prefer
    1048             :   // to have it eliminated.
    1049         336 :   if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
    1050           0 :     if (isEliminableCastPair(PrecedingCI, CI))
    1051             :       return false;
    1052             : 
    1053             :   // If this is a vector sext from a compare, then we don't want to break the
    1054             :   // idiom where each element of the extended vector is either zero or all ones.
    1055         360 :   if (CI->getOpcode() == Instruction::SExt &&
    1056         176 :       isa<CmpInst>(CastSrc) && CI->getDestTy()->isVectorTy())
    1057             :     return false;
    1058             : 
    1059         164 :   return true;
    1060             : }
    1061             : 
    1062             : /// Fold {and,or,xor} (cast X), C.
    1063        2226 : static Instruction *foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast,
    1064             :                                           InstCombiner::BuilderTy *Builder) {
    1065             :   Constant *C;
    1066        6678 :   if (!match(Logic.getOperand(1), m_Constant(C)))
    1067             :     return nullptr;
    1068             : 
    1069        1953 :   auto LogicOpc = Logic.getOpcode();
    1070        1953 :   Type *DestTy = Logic.getType();
    1071        1953 :   Type *SrcTy = Cast->getSrcTy();
    1072             : 
    1073             :   // If the first operand is bitcast, move the logic operation ahead of the
    1074             :   // bitcast (do the logic operation in the original type). This can eliminate
    1075             :   // bitcasts and allow combines that would otherwise be impeded by the bitcast.
    1076             :   Value *X;
    1077        5859 :   if (match(Cast, m_BitCast(m_Value(X)))) {
    1078           7 :     Value *NewConstant = ConstantExpr::getBitCast(C, SrcTy);
    1079           7 :     Value *NewOp = Builder->CreateBinOp(LogicOpc, X, NewConstant);
    1080           7 :     return CastInst::CreateBitOrPointerCast(NewOp, DestTy);
    1081             :   }
    1082             : 
    1083             :   // Similarly, move the logic operation ahead of a zext if the constant is
    1084             :   // unchanged in the smaller source type. Performing the logic in a smaller
    1085             :   // type may provide more information to later folds, and the smaller logic
    1086             :   // instruction may be cheaper (particularly in the case of vectors).
    1087        7784 :   if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
    1088         136 :     Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
    1089         136 :     Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
    1090         136 :     if (ZextTruncC == C) {
    1091             :       // LogicOpc (zext X), C --> zext (LogicOpc X, C)
    1092          94 :       Value *NewOp = Builder->CreateBinOp(LogicOpc, X, TruncC);
    1093         188 :       return new ZExtInst(NewOp, DestTy);
    1094             :     }
    1095             :   }
    1096             : 
    1097             :   return nullptr;
    1098             : }
    1099             : 
    1100             : /// Fold {and,or,xor} (cast X), Y.
    1101       77112 : Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
    1102       77112 :   auto LogicOpc = I.getOpcode();
    1103             :   assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
    1104             : 
    1105      154224 :   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
    1106       77112 :   CastInst *Cast0 = dyn_cast<CastInst>(Op0);
    1107       77112 :   if (!Cast0)
    1108             :     return nullptr;
    1109             : 
    1110             :   // This must be a cast from an integer or integer vector source type to allow
    1111             :   // transformation of the logic operation to the source type.
    1112        2960 :   Type *DestTy = I.getType();
    1113        2960 :   Type *SrcTy = Cast0->getSrcTy();
    1114        2960 :   if (!SrcTy->isIntOrIntVectorTy())
    1115             :     return nullptr;
    1116             : 
    1117        2226 :   if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
    1118             :     return Ret;
    1119             : 
    1120        2125 :   CastInst *Cast1 = dyn_cast<CastInst>(Op1);
    1121        2125 :   if (!Cast1)
    1122             :     return nullptr;
    1123             : 
    1124             :   // Both operands of the logic operation are casts. The casts must be of the
    1125             :   // same type for reduction.
    1126         123 :   auto CastOpcode = Cast0->getOpcode();
    1127         230 :   if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
    1128             :     return nullptr;
    1129             : 
    1130         172 :   Value *Cast0Src = Cast0->getOperand(0);
    1131         172 :   Value *Cast1Src = Cast1->getOperand(0);
    1132             : 
    1133             :   // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
    1134          86 :   if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
    1135         164 :     Value *NewOp = Builder->CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
    1136         246 :                                         I.getName());
    1137          82 :     return CastInst::Create(CastOpcode, NewOp, DestTy);
    1138             :   }
    1139             : 
    1140             :   // For now, only 'and'/'or' have optimizations after this.
    1141           4 :   if (LogicOpc == Instruction::Xor)
    1142             :     return nullptr;
    1143             : 
    1144             :   // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
    1145             :   // cast is otherwise not optimizable.  This happens for vector sexts.
    1146           4 :   ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
    1147           4 :   ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
    1148           4 :   if (ICmp0 && ICmp1) {
    1149           0 :     Value *Res = LogicOpc == Instruction::And ? FoldAndOfICmps(ICmp0, ICmp1)
    1150           0 :                                               : FoldOrOfICmps(ICmp0, ICmp1, &I);
    1151           0 :     if (Res)
    1152           0 :       return CastInst::Create(CastOpcode, Res, DestTy);
    1153             :     return nullptr;
    1154             :   }
    1155             : 
    1156             :   // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
    1157             :   // cast is otherwise not optimizable.  This happens for vector sexts.
    1158           4 :   FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
    1159           4 :   FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
    1160           4 :   if (FCmp0 && FCmp1) {
    1161           4 :     Value *Res = LogicOpc == Instruction::And ? FoldAndOfFCmps(FCmp0, FCmp1)
    1162           4 :                                               : FoldOrOfFCmps(FCmp0, FCmp1);
    1163           4 :     if (Res)
    1164           3 :       return CastInst::Create(CastOpcode, Res, DestTy);
    1165             :     return nullptr;
    1166             :   }
    1167             : 
    1168             :   return nullptr;
    1169             : }
    1170             : 
    1171       37188 : static Instruction *foldBoolSextMaskToSelect(BinaryOperator &I) {
    1172       74376 :   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
    1173             : 
    1174             :   // Canonicalize SExt or Not to the LHS
    1175      185932 :   if (match(Op1, m_SExt(m_Value())) || match(Op1, m_Not(m_Value()))) {
    1176             :     std::swap(Op0, Op1);
    1177             :   }
    1178             : 
    1179             :   // Fold (and (sext bool to A), B) --> (select bool, B, 0)
    1180       37188 :   Value *X = nullptr;
    1181      148873 :   if (match(Op0, m_SExt(m_Value(X))) &&
    1182         242 :       X->getType()->getScalarType()->isIntegerTy(1)) {
    1183          61 :     Value *Zero = Constant::getNullValue(Op1->getType());
    1184         122 :     return SelectInst::Create(X, Op1, Zero);
    1185             :   }
    1186             : 
    1187             :   // Fold (and ~(sext bool to A), B) --> (select bool, 0, B)
    1188      185694 :   if (match(Op0, m_Not(m_SExt(m_Value(X)))) &&
    1189         118 :       X->getType()->getScalarType()->isIntegerTy(1)) {
    1190          56 :     Value *Zero = Constant::getNullValue(Op0->getType());
    1191         112 :     return SelectInst::Create(X, Zero, Op1);
    1192             :   }
    1193             : 
    1194             :   return nullptr;
    1195             : }
    1196             : 
    1197       37675 : static Instruction *foldAndToXor(BinaryOperator &I,
    1198             :                                  InstCombiner::BuilderTy &Builder) {
    1199             :   assert(I.getOpcode() == Instruction::And);
    1200       37675 :   Value *Op0 = I.getOperand(0);
    1201       37675 :   Value *Op1 = I.getOperand(1);
    1202             :   Value *A, *B;
    1203             : 
    1204             :   // Operand complexity canonicalization guarantees that the 'or' is Op0.
    1205             :   // (A | B) & ~(A & B) --> A ^ B
    1206             :   // (A | B) & ~(B & A) --> A ^ B
    1207      188645 :   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
    1208         810 :       match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B)))))
    1209          10 :     return BinaryOperator::CreateXor(A, B);
    1210             : 
    1211             :   // (A | ~B) & (~A | B) --> ~(A ^ B)
    1212             :   // (A | ~B) & (B | ~A) --> ~(A ^ B)
    1213             :   // (~B | A) & (~A | B) --> ~(A ^ B)
    1214             :   // (~B | A) & (B | ~A) --> ~(A ^ B)
    1215      226044 :   if (match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) &&
    1216          60 :       match(Op1, m_c_Or(m_Not(m_Specific(A)), m_Value(B))))
    1217           8 :     return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
    1218             : 
    1219             :   return nullptr;
    1220             : }
    1221             : 
    1222       23189 : static Instruction *foldOrToXor(BinaryOperator &I,
    1223             :                                 InstCombiner::BuilderTy &Builder) {
    1224             :   assert(I.getOpcode() == Instruction::Or);
    1225       23189 :   Value *Op0 = I.getOperand(0);
    1226       23189 :   Value *Op1 = I.getOperand(1);
    1227             :   Value *A, *B;
    1228             : 
    1229             :   // Operand complexity canonicalization guarantees that the 'and' is Op0.
    1230             :   // (A & B) | ~(A | B) --> ~(A ^ B)
    1231             :   // (A & B) | ~(B | A) --> ~(A ^ B)
    1232      132119 :   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
    1233       48522 :       match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
    1234          12 :     return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
    1235             : 
    1236             :   // (A & ~B) | (~A & B) --> A ^ B
    1237             :   // (A & ~B) | (B & ~A) --> A ^ B
    1238             :   // (~B & A) | (~A & B) --> A ^ B
    1239             :   // (~B & A) | (B & ~A) --> A ^ B
    1240      139150 :   if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
    1241         156 :       match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))
    1242           8 :     return BinaryOperator::CreateXor(A, B);
    1243             : 
    1244             :   return nullptr;
    1245             : }
    1246             : 
    1247             : // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
    1248             : // here. We should standardize that construct where it is needed or choose some
    1249             : // other way to ensure that commutated variants of patterns are not missed.
    1250       38437 : Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
    1251       38437 :   bool Changed = SimplifyAssociativeOrCommutative(I);
    1252       76874 :   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
    1253             : 
    1254       38437 :   if (Value *V = SimplifyVectorOp(I))
    1255           1 :     return replaceInstUsesWith(I, V);
    1256             : 
    1257       38436 :   if (Value *V = SimplifyAndInst(Op0, Op1, SQ))
    1258         480 :     return replaceInstUsesWith(I, V);
    1259             : 
    1260             :   // See if we can simplify any instructions used by the instruction whose sole
    1261             :   // purpose is to compute bits we don't care about.
    1262       37956 :   if (SimplifyDemandedInstructionBits(I))
    1263             :     return &I;
    1264             : 
    1265             :   // Do this before using distributive laws to catch simple and/or/not patterns.
    1266       37675 :   if (Instruction *Xor = foldAndToXor(I, *Builder))
    1267             :     return Xor;
    1268             : 
    1269             :   // (A|B)&(A|C) -> A|(B&C) etc
    1270       37666 :   if (Value *V = SimplifyUsingDistributiveLaws(I))
    1271           6 :     return replaceInstUsesWith(I, V);
    1272             : 
    1273       37660 :   if (Value *V = SimplifyBSwap(I))
    1274           6 :     return replaceInstUsesWith(I, V);
    1275             : 
    1276       75308 :   if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) {
    1277       25019 :     const APInt &AndRHSMask = AndRHS->getValue();
    1278             : 
    1279             :     // Optimize a variety of ((val OP C1) & C2) combinations...
    1280       25019 :     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
    1281        6780 :       Value *Op0LHS = Op0I->getOperand(0);
    1282        6780 :       Value *Op0RHS = Op0I->getOperand(1);
    1283        6780 :       switch (Op0I->getOpcode()) {
    1284             :       default: break;
    1285             :       case Instruction::Xor:
    1286             :       case Instruction::Or: {
    1287             :         // If the mask is only needed on one incoming arm, push it up.
    1288         220 :         if (!Op0I->hasOneUse()) break;
    1289             : 
    1290         228 :         APInt NotAndRHS(~AndRHSMask);
    1291         152 :         if (MaskedValueIsZero(Op0LHS, NotAndRHS, 0, &I)) {
    1292             :           // Not masking anything out for the LHS, move to RHS.
    1293           1 :           Value *NewRHS = Builder->CreateAnd(Op0RHS, AndRHS,
    1294           3 :                                              Op0RHS->getName()+".masked");
    1295           2 :           return BinaryOperator::Create(Op0I->getOpcode(), Op0LHS, NewRHS);
    1296             :         }
    1297         203 :         if (!isa<Constant>(Op0RHS) &&
    1298         106 :             MaskedValueIsZero(Op0RHS, NotAndRHS, 0, &I)) {
    1299             :           // Not masking anything out for the RHS, move to LHS.
    1300           2 :           Value *NewLHS = Builder->CreateAnd(Op0LHS, AndRHS,
    1301           6 :                                              Op0LHS->getName()+".masked");
    1302           4 :           return BinaryOperator::Create(Op0I->getOpcode(), NewLHS, Op0RHS);
    1303             :         }
    1304             : 
    1305             :         break;
    1306             :       }
    1307             :       case Instruction::Sub:
    1308             :         // -x & 1 -> x & 1
    1309         253 :         if (AndRHSMask == 1 && match(Op0LHS, m_Zero()))
    1310           4 :           return BinaryOperator::CreateAnd(Op0RHS, AndRHS);
    1311             : 
    1312             :         break;
    1313             : 
    1314             :       case Instruction::Shl:
    1315             :       case Instruction::LShr:
    1316             :         // (1 << x) & 1 --> zext(x == 0)
    1317             :         // (1 >> x) & 1 --> zext(x == 0)
    1318        3941 :         if (AndRHSMask == 1 && Op0LHS == AndRHS) {
    1319             :           Value *NewICmp =
    1320           2 :             Builder->CreateICmpEQ(Op0RHS, Constant::getNullValue(I.getType()));
    1321           3 :           return new ZExtInst(NewICmp, I.getType());
    1322             :         }
    1323             :         break;
    1324             :       }
    1325             : 
    1326             :       // ((C1 OP zext(X)) & C2) -> zext((C1-X) & C2) if C2 fits in the bitwidth
    1327             :       // of X and OP behaves well when given trunc(C1) and X.
    1328        6774 :       switch (Op0I->getOpcode()) {
    1329             :       default:
    1330        4116 :         break;
    1331             :       case Instruction::Xor:
    1332             :       case Instruction::Or:
    1333             :       case Instruction::Mul:
    1334             :       case Instruction::Add:
    1335             :       case Instruction::Sub:
    1336             :         Value *X;
    1337             :         ConstantInt *C1;
    1338       13290 :         if (match(Op0I, m_c_BinOp(m_ZExt(m_Value(X)), m_ConstantInt(C1)))) {
    1339         284 :           if (AndRHSMask.isIntN(X->getType()->getScalarSizeInBits())) {
    1340         141 :             auto *TruncC1 = ConstantExpr::getTrunc(C1, X->getType());
    1341             :             Value *BinOp;
    1342         282 :             if (isa<ZExtInst>(Op0LHS))
    1343         280 :               BinOp = Builder->CreateBinOp(Op0I->getOpcode(), X, TruncC1);
    1344             :             else
    1345           2 :               BinOp = Builder->CreateBinOp(Op0I->getOpcode(), TruncC1, X);
    1346         141 :             auto *TruncC2 = ConstantExpr::getTrunc(AndRHS, X->getType());
    1347         141 :             auto *And = Builder->CreateAnd(BinOp, TruncC2);
    1348         423 :             return new ZExtInst(And, I.getType());
    1349             :           }
    1350             :         }
    1351             :       }
    1352             : 
    1353       13266 :       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
    1354        5777 :         if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
    1355             :           return Res;
    1356             :     }
    1357             : 
    1358             :     // If this is an integer truncation, and if the source is an 'and' with
    1359             :     // immediate, transform it.  This frequently occurs for bitfield accesses.
    1360             :     {
    1361       24834 :       Value *X = nullptr; ConstantInt *YC = nullptr;
    1362      124170 :       if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) {
    1363             :         // Change: and (trunc (and X, YC) to T), C2
    1364             :         // into  : and (trunc X to T), trunc(YC) & C2
    1365             :         // This will fold the two constants together, which may allow
    1366             :         // other simplifications.
    1367           0 :         Value *NewCast = Builder->CreateTrunc(X, I.getType(), "and.shrunk");
    1368           0 :         Constant *C3 = ConstantExpr::getTrunc(YC, I.getType());
    1369           0 :         C3 = ConstantExpr::getAnd(C3, AndRHS);
    1370           0 :         return BinaryOperator::CreateAnd(NewCast, C3);
    1371             :       }
    1372             :     }
    1373             :   }
    1374             : 
    1375       74938 :   if (isa<Constant>(Op1))
    1376       25223 :     if (Instruction *FoldedLogic = foldOpWithConstantIntoOperand(I))
    1377             :       return FoldedLogic;
    1378             : 
    1379       37465 :   if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
    1380             :     return DeMorgan;
    1381             : 
    1382             :   {
    1383       37456 :     Value *A = nullptr, *B = nullptr, *C = nullptr;
    1384             :     // A&(A^B) => A & ~B
    1385             :     {
    1386       37456 :       Value *tmpOp0 = Op0;
    1387       37456 :       Value *tmpOp1 = Op1;
    1388      187280 :       if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
    1389         774 :         if (A == Op1 || B == Op1 ) {
    1390           4 :           tmpOp1 = Op0;
    1391           4 :           tmpOp0 = Op1;
    1392             :           // Simplify below
    1393             :         }
    1394             :       }
    1395             : 
    1396      187280 :       if (match(tmpOp1, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
    1397        2598 :         if (B == tmpOp0) {
    1398             :           std::swap(A, B);
    1399             :         }
    1400             :         // Notice that the pattern (A&(~B)) is actually (A&(-1^B)), so if
    1401             :         // A is originally -1 (or a vector of -1 and undefs), then we enter
    1402             :         // an endless loop. By checking that A is non-constant we ensure that
    1403             :         // we will never get to the loop.
    1404        2602 :         if (A == tmpOp0 && !isa<Constant>(A)) // A&(A^B) -> A & ~B
    1405           3 :           return BinaryOperator::CreateAnd(A, Builder->CreateNot(B));
    1406             :       }
    1407             :     }
    1408             : 
    1409             :     // (A&((~A)|B)) -> A&B
    1410      187275 :     if (match(Op0, m_c_Or(m_Not(m_Specific(Op1)), m_Value(A))))
    1411          16 :       return BinaryOperator::CreateAnd(A, Op1);
    1412      187235 :     if (match(Op1, m_c_Or(m_Not(m_Specific(Op0)), m_Value(A))))
    1413           0 :       return BinaryOperator::CreateAnd(A, Op0);
    1414             : 
    1415             :     // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
    1416      149788 :     if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
    1417        5607 :       if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
    1418           3 :         if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
    1419           3 :           return BinaryOperator::CreateAnd(Op0, Builder->CreateNot(C));
    1420             : 
    1421             :     // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
    1422      224676 :     if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
    1423          30 :       if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
    1424           2 :         if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
    1425           3 :           return BinaryOperator::CreateAnd(Op1, Builder->CreateNot(C));
    1426             : 
    1427             :     // (A | B) & ((~A) ^ B) -> (A & B)
    1428             :     // (A | B) & (B ^ (~A)) -> (A & B)
    1429             :     // (B | A) & ((~A) ^ B) -> (A & B)
    1430             :     // (B | A) & (B ^ (~A)) -> (A & B)
    1431      224678 :     if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
    1432          20 :         match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
    1433           4 :       return BinaryOperator::CreateAnd(A, B);
    1434             : 
    1435             :     // ((~A) ^ B) & (A | B) -> (A & B)
    1436             :     // ((~A) ^ B) & (B | A) -> (A & B)
    1437             :     // (B ^ (~A)) & (A | B) -> (A & B)
    1438             :     // (B ^ (~A)) & (B | A) -> (A & B)
    1439      224665 :     if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
    1440          35 :         match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
    1441           6 :       return BinaryOperator::CreateAnd(A, B);
    1442             :   }
    1443             : 
    1444             :   {
    1445       37440 :     ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
    1446       74880 :     ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
    1447       37440 :     if (LHS && RHS)
    1448        1197 :       if (Value *Res = FoldAndOfICmps(LHS, RHS))
    1449         133 :         return replaceInstUsesWith(I, Res);
    1450             : 
    1451             :     // TODO: Make this recursive; it's a little tricky because an arbitrary
    1452             :     // number of 'and' instructions might have to be created.
    1453             :     Value *X, *Y;
    1454       45329 :     if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
    1455           0 :       if (auto *Cmp = dyn_cast<ICmpInst>(X))
    1456           0 :         if (Value *Res = FoldAndOfICmps(LHS, Cmp))
    1457           0 :           return replaceInstUsesWith(I, Builder->CreateAnd(Res, Y));
    1458           0 :       if (auto *Cmp = dyn_cast<ICmpInst>(Y))
    1459           0 :         if (Value *Res = FoldAndOfICmps(LHS, Cmp))
    1460           0 :           return replaceInstUsesWith(I, Builder->CreateAnd(Res, X));
    1461             :     }
    1462       43359 :     if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
    1463           2 :       if (auto *Cmp = dyn_cast<ICmpInst>(X))
    1464           1 :         if (Value *Res = FoldAndOfICmps(Cmp, RHS))
    1465           1 :           return replaceInstUsesWith(I, Builder->CreateAnd(Res, Y));
    1466           0 :       if (auto *Cmp = dyn_cast<ICmpInst>(Y))
    1467           0 :         if (Value *Res = FoldAndOfICmps(Cmp, RHS))
    1468           0 :           return replaceInstUsesWith(I, Builder->CreateAnd(Res, X));
    1469             :     }
    1470             :   }
    1471             : 
    1472             :   // If and'ing two fcmp, try combine them into one.
    1473       74746 :   if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
    1474         982 :     if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
    1475         485 :       if (Value *Res = FoldAndOfFCmps(LHS, RHS))
    1476         106 :         return replaceInstUsesWith(I, Res);
    1477             : 
    1478       37267 :   if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
    1479             :     return CastedAnd;
    1480             : 
    1481       37188 :   if (Instruction *Select = foldBoolSextMaskToSelect(I))
    1482             :     return Select;
    1483             : 
    1484       37071 :   return Changed ? &I : nullptr;
    1485             : }
    1486             : 
    1487             : /// Given an OR instruction, check to see if this is a bswap idiom. If so,
    1488             : /// insert the new intrinsic and return it.
    1489       23077 : Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
    1490       46154 :   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
    1491             : 
    1492             :   // Look through zero extends.
    1493       23077 :   if (Instruction *Ext = dyn_cast<ZExtInst>(Op0))
    1494         142 :     Op0 = Ext->getOperand(0);
    1495             : 
    1496       23077 :   if (Instruction *Ext = dyn_cast<ZExtInst>(Op1))
    1497         500 :     Op1 = Ext->getOperand(0);
    1498             : 
    1499             :   // (A | B) | C  and  A | (B | C)                  -> bswap if possible.
    1500       91906 :   bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
    1501       91102 :                  match(Op1, m_Or(m_Value(), m_Value()));
    1502             : 
    1503             :   // (A >> B) | (C << D)  and  (A << B) | (B >> C)  -> bswap if possible.
    1504       73649 :   bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
    1505       36331 :                     match(Op1, m_LogicalShift(m_Value(), m_Value()));
    1506             : 
    1507             :   // (A & B) | (C & D)                              -> bswap if possible.
    1508       77311 :   bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
    1509       47317 :                   match(Op1, m_And(m_Value(), m_Value()));
    1510             : 
    1511       23077 :   if (!OrOfOrs && !OrOfShifts && !OrOfAnds)
    1512             :     return nullptr;
    1513             : 
    1514        2324 :   SmallVector<Instruction*, 4> Insts;
    1515        2324 :   if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts))
    1516             :     return nullptr;
    1517          13 :   Instruction *LastInst = Insts.pop_back_val();
    1518          13 :   LastInst->removeFromParent();
    1519             : 
    1520          44 :   for (auto *Inst : Insts)
    1521           5 :     Worklist.Add(Inst);
    1522             :   return LastInst;
    1523             : }
    1524             : 
    1525             : /// If all elements of two constant vectors are 0/-1 and inverses, return true.
    1526           8 : static bool areInverseVectorBitmasks(Constant *C1, Constant *C2) {
    1527          16 :   unsigned NumElts = C1->getType()->getVectorNumElements();
    1528          27 :   for (unsigned i = 0; i != NumElts; ++i) {
    1529          23 :     Constant *EltC1 = C1->getAggregateElement(i);
    1530          23 :     Constant *EltC2 = C2->getAggregateElement(i);
    1531          23 :     if (!EltC1 || !EltC2)
    1532             :       return false;
    1533             : 
    1534             :     // One element must be all ones, and the other must be all zeros.
    1535             :     // FIXME: Allow undef elements.
    1536          94 :     if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
    1537          56 :           (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
    1538             :       return false;
    1539             :   }
    1540             :   return true;
    1541             : }
    1542             : 
    1543             : /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
    1544             : /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
    1545             : /// B, it can be used as the condition operand of a select instruction.
    1546        8823 : static Value *getSelectCondition(Value *A, Value *B,
    1547             :                                  InstCombiner::BuilderTy &Builder) {
    1548             :   // If these are scalars or vectors of i1, A can be used directly.
    1549        8823 :   Type *Ty = A->getType();
    1550       35738 :   if (match(A, m_Not(m_Specific(B))) && Ty->getScalarType()->isIntegerTy(1))
    1551             :     return A;
    1552             : 
    1553             :   // If A and B are sign-extended, look through the sexts to find the booleans.
    1554             :   Value *Cond;
    1555       35288 :   if (match(A, m_SExt(m_Value(Cond))) &&
    1556       26485 :       Cond->getType()->getScalarType()->isIntegerTy(1) &&
    1557          48 :       match(B, m_CombineOr(m_Not(m_SExt(m_Specific(Cond))),
    1558          32 :                            m_SExt(m_Not(m_Specific(Cond))))))
    1559           8 :     return Cond;
    1560             : 
    1561             :   // All scalar (and most vector) possibilities should be handled now.
    1562             :   // Try more matches that only apply to non-splat constant vectors.
    1563        8811 :   if (!Ty->isVectorTy())
    1564             :     return nullptr;
    1565             : 
    1566             :   // If both operands are constants, see if the constants are inverse bitmasks.
    1567             :   Constant *AC, *BC;
    1568       10479 :   if (match(A, m_Constant(AC)) && match(B, m_Constant(BC)) &&
    1569           6 :       areInverseVectorBitmasks(AC, BC))
    1570           2 :     return ConstantExpr::getTrunc(AC, CmpInst::makeCmpResultType(Ty));
    1571             : 
    1572             :   // If both operands are xor'd with constants using the same sexted boolean
    1573             :   // operand, see if the constants are inverse bitmasks.
    1574       20898 :   if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AC)))) &&
    1575          32 :       match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BC)))) &&
    1576       10449 :       Cond->getType()->getScalarType()->isIntegerTy(1) &&
    1577           2 :       areInverseVectorBitmasks(AC, BC)) {
    1578           2 :     AC = ConstantExpr::getTrunc(AC, CmpInst::makeCmpResultType(Ty));
    1579           2 :     return Builder.CreateXor(Cond, AC);
    1580             :   }
    1581             :   return nullptr;
    1582             : }
    1583             : 
    1584             : /// We have an expression of the form (A & C) | (B & D). Try to simplify this
    1585             : /// to "A' ? C : D", where A' is a boolean or vector of booleans.
    1586        8823 : static Value *matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D,
    1587             :                                    InstCombiner::BuilderTy &Builder) {
    1588             :   // The potential condition of the select may be bitcasted. In that case, look
    1589             :   // through its bitcast and the corresponding bitcast of the 'not' condition.
    1590        8823 :   Type *OrigType = A->getType();
    1591             :   Value *SrcA, *SrcB;
    1592       44405 :   if (match(A, m_OneUse(m_BitCast(m_Value(SrcA)))) &&
    1593         580 :       match(B, m_OneUse(m_BitCast(m_Value(SrcB))))) {
    1594          73 :     A = SrcA;
    1595          73 :     B = SrcB;
    1596             :   }
    1597             : 
    1598        8823 :   if (Value *Cond = getSelectCondition(A, B, Builder)) {
    1599             :     // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
    1600             :     // The bitcasts will either all exist or all not exist. The builder will
    1601             :     // not create unnecessary casts if the types already match.
    1602          32 :     Value *BitcastC = Builder.CreateBitCast(C, A->getType());
    1603          32 :     Value *BitcastD = Builder.CreateBitCast(D, A->getType());
    1604          16 :     Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
    1605          32 :     return Builder.CreateBitCast(Select, OrigType);
    1606             :   }
    1607             : 
    1608             :   return nullptr;
    1609             : }
    1610             : 
    1611             : /// Fold (icmp)|(icmp) if possible.
    1612        2234 : Value *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
    1613             :                                    Instruction *CxtI) {
    1614        6702 :   ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
    1615             : 
    1616             :   // Fold (iszero(A & K1) | iszero(A & K2)) ->  (A & (K1 | K2)) != (K1 | K2)
    1617             :   // if K1 and K2 are a one-bit mask.
    1618        6702 :   ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
    1619        6702 :   ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
    1620             : 
    1621        7297 :   if (LHS->getPredicate() == ICmpInst::ICMP_EQ && LHSC && LHSC->isZero() &&
    1622        2558 :       RHS->getPredicate() == ICmpInst::ICMP_EQ && RHSC && RHSC->isZero()) {
    1623             : 
    1624         117 :     BinaryOperator *LAnd = dyn_cast<BinaryOperator>(LHS->getOperand(0));
    1625         117 :     BinaryOperator *RAnd = dyn_cast<BinaryOperator>(RHS->getOperand(0));
    1626         118 :     if (LAnd && RAnd && LAnd->hasOneUse() && RHS->hasOneUse() &&
    1627          49 :         LAnd->getOpcode() == Instruction::And &&
    1628           5 :         RAnd->getOpcode() == Instruction::And) {
    1629             : 
    1630           5 :       Value *Mask = nullptr;
    1631           5 :       Value *Masked = nullptr;
    1632          19 :       if (LAnd->getOperand(0) == RAnd->getOperand(0) &&
    1633           8 :           isKnownToBeAPowerOfTwo(LAnd->getOperand(1), DL, false, 0, &AC, CxtI,
    1634           7 :                                  &DT) &&
    1635           4 :           isKnownToBeAPowerOfTwo(RAnd->getOperand(1), DL, false, 0, &AC, CxtI,
    1636           2 :                                  &DT)) {
    1637           6 :         Mask = Builder->CreateOr(LAnd->getOperand(1), RAnd->getOperand(1));
    1638           4 :         Masked = Builder->CreateAnd(LAnd->getOperand(0), Mask);
    1639          10 :       } else if (LAnd->getOperand(1) == RAnd->getOperand(1) &&
    1640           2 :                  isKnownToBeAPowerOfTwo(LAnd->getOperand(0), DL, false, 0, &AC,
    1641           4 :                                         CxtI, &DT) &&
    1642           2 :                  isKnownToBeAPowerOfTwo(RAnd->getOperand(0), DL, false, 0, &AC,
    1643           1 :                                         CxtI, &DT)) {
    1644           3 :         Mask = Builder->CreateOr(LAnd->getOperand(0), RAnd->getOperand(0));
    1645           2 :         Masked = Builder->CreateAnd(LAnd->getOperand(1), Mask);
    1646             :       }
    1647             : 
    1648           5 :       if (Masked)
    1649           3 :         return Builder->CreateICmp(ICmpInst::ICMP_NE, Masked, Mask);
    1650             :     }
    1651             :   }
    1652             : 
    1653             :   // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
    1654             :   //                   -->  (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
    1655             :   // The original condition actually refers to the following two ranges:
    1656             :   // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
    1657             :   // We can fold these two ranges if:
    1658             :   // 1) C1 and C2 is unsigned greater than C3.
    1659             :   // 2) The two ranges are separated.
    1660             :   // 3) C1 ^ C2 is one-bit mask.
    1661             :   // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
    1662             :   // This implies all values in the two ranges differ by exactly one bit.
    1663             : 
    1664        5127 :   if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) &&
    1665          20 :       PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() &&
    1666        2239 :       LHSC->getType() == RHSC->getType() &&
    1667           8 :       LHSC->getValue() == (RHSC->getValue())) {
    1668             : 
    1669           4 :     Value *LAdd = LHS->getOperand(0);
    1670           4 :     Value *RAdd = RHS->getOperand(0);
    1671             : 
    1672             :     Value *LAddOpnd, *RAddOpnd;
    1673             :     ConstantInt *LAddC, *RAddC;
    1674          14 :     if (match(LAdd, m_Add(m_Value(LAddOpnd), m_ConstantInt(LAddC))) &&
    1675          10 :         match(RAdd, m_Add(m_Value(RAddOpnd), m_ConstantInt(RAddC))) &&
    1676          16 :         LAddC->getValue().ugt(LHSC->getValue()) &&
    1677           6 :         RAddC->getValue().ugt(LHSC->getValue())) {
    1678             : 
    1679          12 :       APInt DiffC = LAddC->getValue() ^ RAddC->getValue();
    1680           2 :       if (LAddOpnd == RAddOpnd && DiffC.isPowerOf2()) {
    1681           2 :         ConstantInt *MaxAddC = nullptr;
    1682           8 :         if (LAddC->getValue().ult(RAddC->getValue()))
    1683             :           MaxAddC = RAddC;
    1684             :         else
    1685           1 :           MaxAddC = LAddC;
    1686             : 
    1687           8 :         APInt RRangeLow = -RAddC->getValue();
    1688          10 :         APInt RRangeHigh = RRangeLow + LHSC->getValue();
    1689          10 :         APInt LRangeLow = -LAddC->getValue();
    1690           8 :         APInt LRangeHigh = LRangeLow + LHSC->getValue();
    1691           6 :         APInt LowRangeDiff = RRangeLow ^ LRangeLow;
    1692           6 :         APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
    1693           2 :         APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
    1694           8 :                                                    : RRangeLow - LRangeLow;
    1695             : 
    1696           6 :         if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
    1697           4 :             RangeDiff.ugt(LHSC->getValue())) {
    1698          10 :           Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC);
    1699             : 
    1700           2 :           Value *NewAnd = Builder->CreateAnd(LAddOpnd, MaskC);
    1701           2 :           Value *NewAdd = Builder->CreateAdd(NewAnd, MaxAddC);
    1702           4 :           return (Builder->CreateICmp(LHS->getPredicate(), NewAdd, LHSC));
    1703             :         }
    1704             :       }
    1705             :     }
    1706             :   }
    1707             : 
    1708             :   // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
    1709        2229 :   if (PredicatesFoldable(PredL, PredR)) {
    1710        6540 :     if (LHS->getOperand(0) == RHS->getOperand(1) &&
    1711           9 :         LHS->getOperand(1) == RHS->getOperand(0))
    1712           0 :       LHS->swapOperands();
    1713        7446 :     if (LHS->getOperand(0) == RHS->getOperand(0) &&
    1714        2727 :         LHS->getOperand(1) == RHS->getOperand(1)) {
    1715           9 :       Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
    1716           3 :       unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
    1717           8 :       bool isSigned = LHS->isSigned() || RHS->isSigned();
    1718           3 :       return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
    1719             :     }
    1720             :   }
    1721             : 
    1722             :   // handle (roughly):
    1723             :   // (icmp ne (A & B), C) | (icmp ne (A & D), E)
    1724        2226 :   if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
    1725             :     return V;
    1726             : 
    1727        6600 :   Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
    1728        4475 :   if (LHS->hasOneUse() || RHS->hasOneUse()) {
    1729             :     // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
    1730             :     // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
    1731        2129 :     Value *A = nullptr, *B = nullptr;
    1732        2299 :     if (PredL == ICmpInst::ICMP_EQ && LHSC && LHSC->isZero()) {
    1733         110 :       B = LHS0;
    1734         126 :       if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS->getOperand(1))
    1735             :         A = RHS0;
    1736         109 :       else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0)
    1737           2 :         A = RHS->getOperand(1);
    1738             :     }
    1739             :     // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
    1740             :     // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
    1741        2766 :     else if (PredR == ICmpInst::ICMP_EQ && RHSC && RHSC->isZero()) {
    1742         675 :       B = RHS0;
    1743         715 :       if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS->getOperand(1))
    1744             :         A = LHS0;
    1745         675 :       else if (PredL == ICmpInst::ICMP_UGT && LHS0 == RHS0)
    1746           2 :         A = LHS->getOperand(1);
    1747             :     }
    1748        2129 :     if (A && B)
    1749          20 :       return Builder->CreateICmp(
    1750             :           ICmpInst::ICMP_UGE,
    1751          10 :           Builder->CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A);
    1752             :   }
    1753             : 
    1754             :   // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
    1755        2195 :   if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
    1756             :     return V;
    1757             : 
    1758             :   // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
    1759        2193 :   if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
    1760             :     return V;
    1761             : 
    1762        2191 :   if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
    1763             :     return V;
    1764             : 
    1765             :   // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
    1766        2174 :   if (!LHSC || !RHSC)
    1767             :     return nullptr;
    1768             : 
    1769         248 :   if (LHSC == RHSC && PredL == PredR) {
    1770             :     // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
    1771          33 :     if (PredL == ICmpInst::ICMP_NE && LHSC->isZero()) {
    1772           0 :       Value *NewOr = Builder->CreateOr(LHS0, RHS0);
    1773           0 :       return Builder->CreateICmp(PredL, NewOr, LHSC);
    1774             :     }
    1775             :   }
    1776             : 
    1777             :   // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
    1778             :   //   iff C2 + CA == C1.
    1779         248 :   if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
    1780             :     ConstantInt *AddC;
    1781         164 :     if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
    1782           9 :       if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
    1783           2 :         return Builder->CreateICmpULE(LHS0, LHSC);
    1784             :   }
    1785             : 
    1786             :   // From here on, we only handle:
    1787             :   //    (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
    1788         247 :   if (LHS0 != RHS0)
    1789             :     return nullptr;
    1790             : 
    1791             :   // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
    1792          14 :   if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
    1793          14 :       PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
    1794          14 :       PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
    1795          14 :       PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
    1796             :     return nullptr;
    1797             : 
    1798             :   // We can't fold (ugt x, C) | (sgt x, C2).
    1799          14 :   if (!PredicatesFoldable(PredL, PredR))
    1800             :     return nullptr;
    1801             : 
    1802             :   // Ensure that the larger constant is on the RHS.
    1803             :   bool ShouldSwap;
    1804          31 :   if (CmpInst::isSigned(PredL) ||
    1805          20 :       (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
    1806          28 :     ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
    1807             :   else
    1808          20 :     ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
    1809             : 
    1810          12 :   if (ShouldSwap) {
    1811           4 :     std::swap(LHS, RHS);
    1812           4 :     std::swap(LHSC, RHSC);
    1813             :     std::swap(PredL, PredR);
    1814             :   }
    1815             : 
    1816             :   // At this point, we know we have two icmp instructions
    1817             :   // comparing a value against two constants and or'ing the result
    1818             :   // together.  Because of the above check, we know that we only have
    1819             :   // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
    1820             :   // icmp folding check above), that the two constants are not
    1821             :   // equal.
    1822             :   assert(LHSC != RHSC && "Compares not folded above?");
    1823             : 
    1824          12 :   switch (PredL) {
    1825             :   default:
    1826           0 :     llvm_unreachable("Unknown integer condition code!");
    1827             :   case ICmpInst::ICMP_EQ:
    1828             :     switch (PredR) {
    1829             :     default:
    1830           0 :       llvm_unreachable("Unknown integer condition code!");
    1831             :     case ICmpInst::ICMP_EQ:
    1832             :       // Potential folds for this case should already be handled.
    1833             :       break;
    1834             :     case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change
    1835             :     case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change
    1836             :       break;
    1837             :     case ICmpInst::ICMP_NE:  // (X == 13 | X != 15) -> X != 15
    1838             :     case ICmpInst::ICMP_ULT: // (X == 13 | X u< 15) -> X u< 15
    1839             :     case ICmpInst::ICMP_SLT: // (X == 13 | X s< 15) -> X s< 15
    1840             :       return RHS;
    1841             :     }
    1842             :     break;
    1843             :   case ICmpInst::ICMP_NE:
    1844             :     switch (PredR) {
    1845             :     default:
    1846           0 :       llvm_unreachable("Unknown integer condition code!");
    1847             :     case ICmpInst::ICMP_EQ:  // (X != 13 | X == 15) -> X != 13
    1848             :     case ICmpInst::ICMP_UGT: // (X != 13 | X u> 15) -> X != 13
    1849             :     case ICmpInst::ICMP_SGT: // (X != 13 | X s> 15) -> X != 13
    1850             :       return LHS;
    1851             :     case ICmpInst::ICMP_NE:  // (X != 13 | X != 15) -> true
    1852             :     case ICmpInst::ICMP_ULT: // (X != 13 | X u< 15) -> true
    1853             :     case ICmpInst::ICMP_SLT: // (X != 13 | X s< 15) -> true
    1854           2 :       return Builder->getTrue();
    1855             :     }
    1856             :   case ICmpInst::ICMP_ULT:
    1857           0 :     switch (PredR) {
    1858             :     default:
    1859           0 :       llvm_unreachable("Unknown integer condition code!");
    1860             :     case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
    1861             :       break;
    1862             :     case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
    1863             :       // If RHSC is [us]MAXINT, it is always false.  Not handling
    1864             :       // this can cause overflow.
    1865           0 :       if (RHSC->isMaxValue(false))
    1866             :         return LHS;
    1867           0 :       return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
    1868           0 :                              false, false);
    1869             :     case ICmpInst::ICMP_NE:  // (X u< 13 | X != 15) -> X != 15
    1870             :     case ICmpInst::ICMP_ULT: // (X u< 13 | X u< 15) -> X u< 15
    1871             :       return RHS;
    1872             :     }
    1873             :     break;
    1874             :   case ICmpInst::ICMP_SLT:
    1875           7 :     switch (PredR) {
    1876             :     default:
    1877           0 :       llvm_unreachable("Unknown integer condition code!");
    1878             :     case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change
    1879             :       break;
    1880             :     case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2
    1881             :       // If RHSC is [us]MAXINT, it is always false.  Not handling
    1882             :       // this can cause overflow.
    1883           5 :       if (RHSC->isMaxValue(true))
    1884             :         return LHS;
    1885          35 :       return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
    1886           5 :                              false);
    1887             :     case ICmpInst::ICMP_NE:  // (X s< 13 | X != 15) -> X != 15
    1888             :     case ICmpInst::ICMP_SLT: // (X s< 13 | X s< 15) -> X s< 15
    1889             :       return RHS;
    1890             :     }
    1891             :     break;
    1892             :   case ICmpInst::ICMP_UGT:
    1893           1 :     switch (PredR) {
    1894             :     default:
    1895           0 :       llvm_unreachable("Unknown integer condition code!");
    1896             :     case ICmpInst::ICMP_EQ:  // (X u> 13 | X == 15) -> X u> 13
    1897             :     case ICmpInst::ICMP_UGT: // (X u> 13 | X u> 15) -> X u> 13
    1898             :       return LHS;
    1899             :     case ICmpInst::ICMP_NE:  // (X u> 13 | X != 15) -> true
    1900             :     case ICmpInst::ICMP_ULT: // (X u> 13 | X u< 15) -> true
    1901           2 :       return Builder->getTrue();
    1902             :     }
    1903             :     break;
    1904             :   case ICmpInst::ICMP_SGT:
    1905           0 :     switch (PredR) {
    1906             :     default:
    1907           0 :       llvm_unreachable("Unknown integer condition code!");
    1908             :     case ICmpInst::ICMP_EQ:  // (X s> 13 | X == 15) -> X > 13
    1909             :     case ICmpInst::ICMP_SGT: // (X s> 13 | X s> 15) -> X > 13
    1910             :       return LHS;
    1911             :     case ICmpInst::ICMP_NE:  // (X s> 13 | X != 15) -> true
    1912             :     case ICmpInst::ICMP_SLT: // (X s> 13 | X s< 15) -> true
    1913           0 :       return Builder->getTrue();
    1914             :     }
    1915             :     break;
    1916             :   }
    1917           5 :   return nullptr;
    1918             : }
    1919             : 
    1920             : /// Optimize (fcmp)|(fcmp).  NOTE: Unlike the rest of instcombine, this returns
    1921             : /// a Value which should already be inserted into the function.
    1922         265 : Value *InstCombiner::FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
    1923         795 :   Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1);
    1924         795 :   Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1);
    1925         795 :   FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate();
    1926             : 
    1927         265 :   if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) {
    1928             :     // Swap RHS operands to match LHS.
    1929           0 :     Op1CC = FCmpInst::getSwappedPredicate(Op1CC);
    1930             :     std::swap(Op1LHS, Op1RHS);
    1931             :   }
    1932             : 
    1933             :   // Simplify (fcmp cc0 x, y) | (fcmp cc1 x, y).
    1934             :   // This is a similar transformation to the one in FoldAndOfFCmps.
    1935             :   //
    1936             :   // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
    1937             :   //    bool(R & CC0) || bool(R & CC1)
    1938             :   //  = bool((R & CC0) | (R & CC1))
    1939             :   //  = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
    1940         265 :   if (Op0LHS == Op1LHS && Op0RHS == Op1RHS)
    1941         106 :     return getFCmpValue(getFCmpCode(Op0CC) | getFCmpCode(Op1CC), Op0LHS, Op0RHS,
    1942         106 :                         Builder);
    1943             : 
    1944         480 :   if (LHS->getPredicate() == FCmpInst::FCMP_UNO &&
    1945         165 :       RHS->getPredicate() == FCmpInst::FCMP_UNO &&
    1946           9 :       LHS->getOperand(0)->getType() == RHS->getOperand(0)->getType()) {
    1947           6 :     if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1)))
    1948           3 :       if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) {
    1949             :         // If either of the constants are nans, then the whole thing returns
    1950             :         // true.
    1951           3 :         if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN())
    1952           0 :           return Builder->getTrue();
    1953             : 
    1954             :         // Otherwise, no need to compare the two constants, compare the
    1955             :         // rest.
    1956           4 :         return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0));
    1957             :       }
    1958             : 
    1959             :     // Handle vector zeros.  This occurs because the canonical form of
    1960             :     // "fcmp uno x,x" is "fcmp uno x, 0".
    1961           4 :     if (isa<ConstantAggregateZero>(LHS->getOperand(1)) &&
    1962           2 :         isa<ConstantAggregateZero>(RHS->getOperand(1)))
    1963           4 :       return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0));
    1964             : 
    1965             :     return nullptr;
    1966             :   }
    1967             : 
    1968             :   return nullptr;
    1969             : }
    1970             : 
    1971             : /// This helper function folds:
    1972             : ///
    1973             : ///     ((A | B) & C1) | (B & C2)
    1974             : ///
    1975             : /// into:
    1976             : ///
    1977             : ///     (A & C1) | B
    1978             : ///
    1979             : /// when the XOR of the two constants is "all ones" (-1).
    1980          14 : Instruction *InstCombiner::FoldOrWithConstants(BinaryOperator &I, Value *Op,
    1981             :                                                Value *A, Value *B, Value *C) {
    1982          14 :   ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
    1983          14 :   if (!CI1) return nullptr;
    1984             : 
    1985           4 :   Value *V1 = nullptr;
    1986           4 :   ConstantInt *CI2 = nullptr;
    1987          16 :   if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2)))) return nullptr;
    1988             : 
    1989          24 :   APInt Xor = CI1->getValue() ^ CI2->getValue();
    1990           4 :   if (!Xor.isAllOnesValue()) return nullptr;
    1991             : 
    1992           4 :   if (V1 == A || V1 == B) {
    1993           4 :     Value *NewOp = Builder->CreateAnd((V1 == A) ? B : A, CI1);
    1994           8 :     return BinaryOperator::CreateOr(NewOp, V1);
    1995             :   }
    1996             : 
    1997             :   return nullptr;
    1998             : }
    1999             : 
    2000             : /// \brief This helper function folds:
    2001             : ///
    2002             : ///     ((A | B) & C1) ^ (B & C2)
    2003             : ///
    2004             : /// into:
    2005             : ///
    2006             : ///     (A & C1) ^ B
    2007             : ///
    2008             : /// when the XOR of the two constants is "all ones" (-1).
    2009         166 : Instruction *InstCombiner::FoldXorWithConstants(BinaryOperator &I, Value *Op,
    2010             :                                                 Value *A, Value *B, Value *C) {
    2011         166 :   ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
    2012         166 :   if (!CI1)
    2013             :     return nullptr;
    2014             : 
    2015           1 :   Value *V1 = nullptr;
    2016           1 :   ConstantInt *CI2 = nullptr;
    2017           4 :   if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2))))
    2018             :     return nullptr;
    2019             : 
    2020           6 :   APInt Xor = CI1->getValue() ^ CI2->getValue();
    2021           1 :   if (!Xor.isAllOnesValue())
    2022             :     return nullptr;
    2023             : 
    2024           1 :   if (V1 == A || V1 == B) {
    2025           1 :     Value *NewOp = Builder->CreateAnd(V1 == A ? B : A, CI1);
    2026           2 :     return BinaryOperator::CreateXor(NewOp, V1);
    2027             :   }
    2028             : 
    2029             :   return nullptr;
    2030             : }
    2031             : 
    2032             : // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
    2033             : // here. We should standardize that construct where it is needed or choose some
    2034             : // other way to ensure that commutated variants of patterns are not missed.
    2035       23511 : Instruction *InstCombiner::visitOr(BinaryOperator &I) {
    2036       23511 :   bool Changed = SimplifyAssociativeOrCommutative(I);
    2037       47022 :   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
    2038             : 
    2039       23511 :   if (Value *V = SimplifyVectorOp(I))
    2040           0 :     return replaceInstUsesWith(I, V);
    2041             : 
    2042       23511 :   if (Value *V = SimplifyOrInst(Op0, Op1, SQ))
    2043         252 :     return replaceInstUsesWith(I, V);
    2044             : 
    2045             :   // See if we can simplify any instructions used by the instruction whose sole
    2046             :   // purpose is to compute bits we don't care about.
    2047       23259 :   if (SimplifyDemandedInstructionBits(I))
    2048             :     return &I;
    2049             : 
    2050             :   // Do this before using distributive laws to catch simple and/or/not patterns.
    2051       23189 :   if (Instruction *Xor = foldOrToXor(I, *Builder))
    2052             :     return Xor;
    2053             : 
    2054             :   // (A&B)|(A&C) -> A&(B|C) etc
    2055       23179 :   if (Value *V = SimplifyUsingDistributiveLaws(I))
    2056          83 :     return replaceInstUsesWith(I, V);
    2057             : 
    2058       23096 :   if (Value *V = SimplifyBSwap(I))
    2059           3 :     return replaceInstUsesWith(I, V);
    2060             : 
    2061       46186 :   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
    2062       10737 :     ConstantInt *C1 = nullptr; Value *X = nullptr;
    2063             :     // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
    2064       53698 :     if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) &&
    2065          26 :         Op0->hasOneUse()) {
    2066          10 :       Value *Or = Builder->CreateOr(X, RHS);
    2067          10 :       Or->takeName(Op0);
    2068          20 :       return BinaryOperator::CreateXor(Or,
    2069         100 :                             Builder->getInt(C1->getValue() & ~RHS->getValue()));
    2070             :     }
    2071             :   }
    2072             : 
    2073       46166 :   if (isa<Constant>(Op1))
    2074       10808 :     if (Instruction *FoldedLogic = foldOpWithConstantIntoOperand(I))
    2075             :       return FoldedLogic;
    2076             : 
    2077             :   // Given an OR instruction, check to see if this is a bswap.
    2078       23077 :   if (Instruction *BSwap = MatchBSwap(I))
    2079             :     return BSwap;
    2080             : 
    2081             :   {
    2082             :     Value *A;
    2083             :     const APInt *C;
    2084             :     // (X^C)|Y -> (X|Y)^C iff Y&C == 0
    2085      138492 :     if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
    2086         216 :         MaskedValueIsZero(Op1, *C, 0, &I)) {
    2087           4 :       Value *NOr = Builder->CreateOr(A, Op1);
    2088           4 :       NOr->takeName(Op0);
    2089           8 :       return BinaryOperator::CreateXor(NOr,
    2090           8 :                                        ConstantInt::get(NOr->getType(), *C));
    2091             :     }
    2092             : 
    2093             :     // Y|(X^C) -> (X|Y)^C iff Y&C == 0
    2094      138503 :     if (match(Op1, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
    2095         286 :         MaskedValueIsZero(Op0, *C, 0, &I)) {
    2096           3 :       Value *NOr = Builder->CreateOr(A, Op0);
    2097           3 :       NOr->takeName(Op0);
    2098           6 :       return BinaryOperator::CreateXor(NOr,
    2099           6 :                                        ConstantInt::get(NOr->getType(), *C));
    2100             :     }
    2101             :   }
    2102             : 
    2103             :   Value *A, *B;
    2104             : 
    2105             :   // ((~A & B) | A) -> (A | B)
    2106      115285 :   if (match(Op0, m_c_And(m_Not(m_Specific(Op1)), m_Value(A))))
    2107           4 :     return BinaryOperator::CreateOr(A, Op1);
    2108      115275 :   if (match(Op1, m_c_And(m_Not(m_Specific(Op0)), m_Value(A))))
    2109           4 :     return BinaryOperator::CreateOr(Op0, A);
    2110             : 
    2111             :   // ((A & B) | ~A) -> (~A | B)
    2112             :   // The NOT is guaranteed to be in the RHS by complexity ordering.
    2113       92352 :   if (match(Op1, m_Not(m_Value(A))) &&
    2114         560 :       match(Op0, m_c_And(m_Specific(A), m_Value(B))))
    2115           8 :     return BinaryOperator::CreateOr(Op1, B);
    2116             : 
    2117             :   // (A & C)|(B & D)
    2118       23049 :   Value *C = nullptr, *D = nullptr;
    2119      123288 :   if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
    2120       32172 :       match(Op1, m_And(m_Value(B), m_Value(D)))) {
    2121        1113 :     Value *V1 = nullptr, *V2 = nullptr;
    2122        2226 :     ConstantInt *C1 = dyn_cast<ConstantInt>(C);
    2123        2226 :     ConstantInt *C2 = dyn_cast<ConstantInt>(D);
    2124        1113 :     if (C1 && C2) {  // (A & C1)|(B & C2)
    2125        3006 :       if ((C1->getValue() & C2->getValue()) == 0) {
    2126             :         // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
    2127             :         // iff (C1&C2) == 0 and (N&~C1) == 0
    2128        3011 :         if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
    2129           6 :             ((V1 == B &&
    2130         512 :               MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
    2131           6 :              (V2 == B &&
    2132         507 :               MaskedValueIsZero(V1, ~C1->getValue(), 0, &I))))  // (N|V)
    2133           0 :           return BinaryOperator::CreateAnd(A,
    2134           0 :                                 Builder->getInt(C1->getValue()|C2->getValue()));
    2135             :         // Or commutes, try both ways.
    2136        3008 :         if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
    2137           3 :             ((V1 == A &&
    2138         509 :               MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
    2139           3 :              (V2 == A &&
    2140         507 :               MaskedValueIsZero(V1, ~C2->getValue(), 0, &I))))  // (N|V)
    2141           0 :           return BinaryOperator::CreateAnd(B,
    2142           0 :                                 Builder->getInt(C1->getValue()|C2->getValue()));
    2143             : 
    2144             :         // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
    2145             :         // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
    2146         501 :         ConstantInt *C3 = nullptr, *C4 = nullptr;
    2147        2508 :         if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
    2148         528 :             (C3->getValue() & ~C1->getValue()) == 0 &&
    2149        1014 :             match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
    2150         501 :             (C4->getValue() & ~C2->getValue()) == 0) {
    2151           0 :           V2 = Builder->CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
    2152           0 :           return BinaryOperator::CreateAnd(V2,
    2153           0 :                                 Builder->getInt(C1->getValue()|C2->getValue()));
    2154             :         }
    2155             :       }
    2156             :     }
    2157             : 
    2158             :     // Don't try to form a select if it's unlikely that we'll get rid of at
    2159             :     // least one of the operands. A select is generally more expensive than the
    2160             :     // 'or' that it is replacing.
    2161        2249 :     if (Op0->hasOneUse() || Op1->hasOneUse()) {
    2162             :       // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
    2163        1112 :       if (Value *V = matchSelectFromAndOr(A, C, B, D, *Builder))
    2164           6 :         return replaceInstUsesWith(I, V);
    2165        1106 :       if (Value *V = matchSelectFromAndOr(A, C, D, B, *Builder))
    2166           1 :         return replaceInstUsesWith(I, V);
    2167        1105 :       if (Value *V = matchSelectFromAndOr(C, A, B, D, *Builder))
    2168           1 :         return replaceInstUsesWith(I, V);
    2169        1104 :       if (Value *V = matchSelectFromAndOr(C, A, D, B, *Builder))
    2170           3 :         return replaceInstUsesWith(I, V);
    2171        1101 :       if (Value *V = matchSelectFromAndOr(B, D, A, C, *Builder))
    2172           1 :         return replaceInstUsesWith(I, V);
    2173        1100 :       if (Value *V = matchSelectFromAndOr(B, D, C, A, *Builder))
    2174           2 :         return replaceInstUsesWith(I, V);
    2175        1098 :       if (Value *V = matchSelectFromAndOr(D, B, A, C, *Builder))
    2176           1 :         return replaceInstUsesWith(I, V);
    2177        1097 :       if (Value *V = matchSelectFromAndOr(D, B, C, A, *Builder))
    2178           1 :         return replaceInstUsesWith(I, V);
    2179             :     }
    2180             : 
    2181             :     // ((A|B)&1)|(B&-2) -> (A&1) | B
    2182        6581 :     if (match(A, m_Or(m_Value(V1), m_Specific(B))) ||
    2183        4384 :         match(A, m_Or(m_Specific(B), m_Value(V1)))) {
    2184          12 :       Instruction *Ret = FoldOrWithConstants(I, Op1, V1, B, C);
    2185          12 :       if (Ret) return Ret;
    2186             :     }
    2187             :     // (B&-2)|((A|B)&1) -> (A&1) | B
    2188        6569 :     if (match(B, m_Or(m_Specific(A), m_Value(V1))) ||
    2189        5470 :         match(B, m_Or(m_Value(V1), m_Specific(A)))) {
    2190           2 :       Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D);
    2191           2 :       if (Ret) return Ret;
    2192             :     }
    2193             :     // ((A^B)&1)|(B&-2) -> (A&1) ^ B
    2194        6557 :     if (match(A, m_Xor(m_Value(V1), m_Specific(B))) ||
    2195        4368 :         match(A, m_Xor(m_Specific(B), m_Value(V1)))) {
    2196           6 :       Instruction *Ret = FoldXorWithConstants(I, Op1, V1, B, C);
    2197           6 :       if (Ret) return Ret;
    2198             :     }
    2199             :     // (B&-2)|((A^B)&1) -> (A&1) ^ B
    2200        6392 :     if (match(B, m_Xor(m_Specific(A), m_Value(V1))) ||
    2201        4660 :         match(B, m_Xor(m_Value(V1), m_Specific(A)))) {
    2202         160 :       Instruction *Ret = FoldXorWithConstants(I, Op0, A, V1, D);
    2203         160 :       if (Ret) return Ret;
    2204             :     }
    2205             :   }
    2206             : 
    2207             :   // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
    2208       92112 :   if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
    2209         840 :     if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
    2210           3 :       if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
    2211           2 :         return BinaryOperator::CreateOr(Op0, C);
    2212             : 
    2213             :   // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
    2214      138162 :   if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
    2215          35 :     if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
    2216           0 :       if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
    2217           0 :         return BinaryOperator::CreateOr(Op1, C);
    2218             : 
    2219             :   // ((B | C) & A) | B -> B | (A & C)
    2220      138162 :   if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
    2221           3 :     return BinaryOperator::CreateOr(Op1, Builder->CreateAnd(A, C));
    2222             : 
    2223       23026 :   if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
    2224             :     return DeMorgan;
    2225             : 
    2226             :   // Canonicalize xor to the RHS.
    2227       23018 :   bool SwappedForXor = false;
    2228       69054 :   if (match(Op0, m_Xor(m_Value(), m_Value()))) {
    2229         111 :     std::swap(Op0, Op1);
    2230         111 :     SwappedForXor = true;
    2231             :   }
    2232             : 
    2233             :   // A | ( A ^ B) -> A |  B
    2234             :   // A | (~A ^ B) -> A | ~B
    2235             :   // (A & B) | (A ^ B)
    2236       92072 :   if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
    2237         253 :     if (Op0 == A || Op0 == B)
    2238           2 :       return BinaryOperator::CreateOr(A, B);
    2239             : 
    2240        1511 :     if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
    2241        1255 :         match(Op0, m_And(m_Specific(B), m_Specific(A))))
    2242           2 :       return BinaryOperator::CreateOr(A, B);
    2243             : 
    2244        1195 :     if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
    2245           4 :       Value *Not = Builder->CreateNot(B, B->getName()+".not");
    2246           4 :       return BinaryOperator::CreateOr(Not, Op0);
    2247             :     }
    2248        1185 :     if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
    2249           0 :       Value *Not = Builder->CreateNot(A, A->getName()+".not");
    2250           0 :       return BinaryOperator::CreateOr(Not, Op0);
    2251             :     }
    2252             :   }
    2253             : 
    2254             :   // A | ~(A | B) -> A | ~B
    2255             :   // A | ~(A ^ B) -> A | ~B
    2256       69042 :   if (match(Op1, m_Not(m_Value(A))))
    2257         420 :     if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
    2258          14 :       if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
    2259          18 :           Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
    2260           2 :                                B->getOpcode() == Instruction::Xor)) {
    2261           4 :         Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
    2262           4 :                                                  B->getOperand(0);
    2263           8 :         Value *Not = Builder->CreateNot(NotOp, NotOp->getName()+".not");
    2264           8 :         return BinaryOperator::CreateOr(Not, Op0);
    2265             :       }
    2266             : 
    2267             :   // (A & B) | (~A ^ B) -> (~A ^ B)
    2268             :   // (A & B) | (B ^ ~A) -> (~A ^ B)
    2269             :   // (B & A) | (~A ^ B) -> (~A ^ B)
    2270             :   // (B & A) | (B ^ ~A) -> (~A ^ B)
    2271             :   // The match order is important: match the xor first because the 'not'
    2272             :   // operation defines 'A'. We do not need to match the xor as Op0 because the
    2273             :   // xor was canonicalized to Op1 above.
    2274      138064 :   if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
    2275          20 :       match(Op0, m_c_And(m_Specific(A), m_Specific(B))))
    2276          12 :     return BinaryOperator::CreateXor(Builder->CreateNot(A), B);
    2277             : 
    2278       23006 :   if (SwappedForXor)
    2279             :     std::swap(Op0, Op1);
    2280             : 
    2281             :   {
    2282       46012 :     ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
    2283       46012 :     ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
    2284       23006 :     if (LHS && RHS)
    2285        2213 :       if (Value *Res = FoldOrOfICmps(LHS, RHS, &I))
    2286         134 :         return replaceInstUsesWith(I, Res);
    2287             : 
    2288             :     // TODO: Make this recursive; it's a little tricky because an arbitrary
    2289             :     // number of 'or' instructions might have to be created.
    2290             :     Value *X, *Y;
    2291       34160 :     if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
    2292          14 :       if (auto *Cmp = dyn_cast<ICmpInst>(X))
    2293           7 :         if (Value *Res = FoldOrOfICmps(LHS, Cmp, &I))
    2294           1 :           return replaceInstUsesWith(I, Builder->CreateOr(Res, Y));
    2295          12 :       if (auto *Cmp = dyn_cast<ICmpInst>(Y))
    2296           6 :         if (Value *Res = FoldOrOfICmps(LHS, Cmp, &I))
    2297           0 :           return replaceInstUsesWith(I, Builder->CreateOr(Res, X));
    2298             :     }
    2299       33929 :     if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
    2300           8 :       if (auto *Cmp = dyn_cast<ICmpInst>(X))
    2301           4 :         if (Value *Res = FoldOrOfICmps(Cmp, RHS, &I))
    2302           0 :           return replaceInstUsesWith(I, Builder->CreateOr(Res, Y));
    2303           8 :       if (auto *Cmp = dyn_cast<ICmpInst>(Y))
    2304           4 :         if (Value *Res = FoldOrOfICmps(Cmp, RHS, &I))
    2305           1 :           return replaceInstUsesWith(I, Builder->CreateOr(Res, X));
    2306             :     }
    2307             :   }
    2308             : 
    2309             :   // (fcmp uno x, c) | (fcmp uno y, c)  -> (fcmp uno x, y)
    2310       45876 :   if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
    2311         530 :     if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
    2312         263 :       if (Value *Res = FoldOrOfFCmps(LHS, RHS))
    2313         106 :         return replaceInstUsesWith(I, Res);
    2314             : 
    2315       22832 :   if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
    2316             :     return CastedOr;
    2317             : 
    2318             :   // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
    2319      113904 :   if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
    2320          28 :       A->getType()->getScalarType()->isIntegerTy(1))
    2321           8 :     return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
    2322      113873 :   if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
    2323           6 :       A->getType()->getScalarType()->isIntegerTy(1))
    2324           0 :     return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
    2325             : 
    2326             :   // Note: If we've gotten to the point of visiting the outer OR, then the
    2327             :   // inner one couldn't be simplified.  If it was a constant, then it won't
    2328             :   // be simplified by a later pass either, so we try swapping the inner/outer
    2329             :   // ORs in the hopes that we'll be able to simplify it this way.
    2330             :   // (X|C) | V --> (X|V) | C
    2331             :   ConstantInt *C1;
    2332       76298 :   if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) &&
    2333       43364 :       match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) {
    2334           4 :     Value *Inner = Builder->CreateOr(A, Op1);
    2335           4 :     Inner->takeName(Op0);
    2336           8 :     return BinaryOperator::CreateOr(Inner, C1);
    2337             :   }
    2338             : 
    2339             :   // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
    2340             :   // Since this OR statement hasn't been optimized further yet, we hope
    2341             :   // that this transformation will allow the new ORs to be optimized.
    2342             :   {
    2343       22770 :     Value *X = nullptr, *Y = nullptr;
    2344      117796 :     if (Op0->hasOneUse() && Op1->hasOneUse() &&
    2345       48388 :         match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
    2346       22810 :         match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
    2347           0 :       Value *orTrue = Builder->CreateOr(A, C);
    2348           0 :       Value *orFalse = Builder->CreateOr(B, D);
    2349           0 :       return SelectInst::Create(X, orTrue, orFalse);
    2350             :     }
    2351             :   }
    2352             : 
    2353       22770 :   return Changed ? &I : nullptr;
    2354             : }
    2355             : 
    2356             : /// A ^ B can be specified using other logic ops in a variety of patterns. We
    2357             : /// can fold these early and efficiently by morphing an existing instruction.
    2358       18196 : static Instruction *foldXorToXor(BinaryOperator &I) {
    2359             :   assert(I.getOpcode() == Instruction::Xor);
    2360       18196 :   Value *Op0 = I.getOperand(0);
    2361       18196 :   Value *Op1 = I.getOperand(1);
    2362             :   Value *A, *B;
    2363             : 
    2364             :   // There are 4 commuted variants for each of the basic patterns.
    2365             : 
    2366             :   // (A & B) ^ (A | B) -> A ^ B
    2367             :   // (A & B) ^ (B | A) -> A ^ B
    2368             :   // (A | B) ^ (A & B) -> A ^ B
    2369             :   // (A | B) ^ (B & A) -> A ^ B
    2370       93664 :   if ((match(Op0, m_And(m_Value(A), m_Value(B))) &&
    2371       96340 :        match(Op1, m_c_Or(m_Specific(A), m_Specific(B)))) ||
    2372       73928 :       (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
    2373        2900 :        match(Op1, m_c_And(m_Specific(A), m_Specific(B))))) {
    2374          12 :     I.setOperand(0, A);
    2375          12 :     I.setOperand(1, B);
    2376           6 :     return &I;
    2377             :   }
    2378             : 
    2379             :   // (A | ~B) ^ (~A | B) -> A ^ B
    2380             :   // (~B | A) ^ (~A | B) -> A ^ B
    2381             :   // (~A | B) ^ (A | ~B) -> A ^ B
    2382             :   // (B | ~A) ^ (A | ~B) -> A ^ B
    2383      109156 :   if ((match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) &&
    2384       90982 :        match(Op1, m_Or(m_Not(m_Specific(A)), m_Specific(B)))) ||
    2385       90938 :       (match(Op0, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
    2386          24 :        match(Op1, m_Or(m_Specific(A), m_Not(m_Specific(B)))))) {
    2387          12 :     I.setOperand(0, A);
    2388          12 :     I.setOperand(1, B);
    2389           6 :     return &I;
    2390             :   }
    2391             : 
    2392             :   // (A & ~B) ^ (~A & B) -> A ^ B
    2393             :   // (~B & A) ^ (~A & B) -> A ^ B
    2394             :   // (~A & B) ^ (A & ~B) -> A ^ B
    2395             :   // (B & ~A) ^ (A & ~B) -> A ^ B
    2396      109152 :   if ((match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
    2397       91032 :        match(Op1, m_And(m_Not(m_Specific(A)), m_Specific(B)))) ||
    2398       90940 :       (match(Op0, m_c_And(m_Not(m_Value(A)), m_Value(B))) &&
    2399         120 :        match(Op1, m_And(m_Specific(A), m_Not(m_Specific(B)))))) {
    2400          12 :     I.setOperand(0, A);
    2401          12 :     I.setOperand(1, B);
    2402           6 :     return &I;
    2403             :   }
    2404             : 
    2405             :   return nullptr;
    2406             : }
    2407             : 
    2408             : // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
    2409             : // here. We should standardize that construct where it is needed or choose some
    2410             : // other way to ensure that commutated variants of patterns are not missed.
    2411       18245 : Instruction *InstCombiner::visitXor(BinaryOperator &I) {
    2412       18245 :   bool Changed = SimplifyAssociativeOrCommutative(I);
    2413       36490 :   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
    2414             : 
    2415       18245 :   if (Value *V = SimplifyVectorOp(I))
    2416           0 :     return replaceInstUsesWith(I, V);
    2417             : 
    2418       18245 :   if (Value *V = SimplifyXorInst(Op0, Op1, SQ))
    2419          49 :     return replaceInstUsesWith(I, V);
    2420             : 
    2421       18196 :   if (Instruction *NewXor = foldXorToXor(I))
    2422             :     return NewXor;
    2423             : 
    2424             :   // (A&B)^(A&C) -> A&(B^C) etc
    2425       18178 :   if (Value *V = SimplifyUsingDistributiveLaws(I))
    2426          21 :     return replaceInstUsesWith(I, V);
    2427             : 
    2428             :   // See if we can simplify any instructions used by the instruction whose sole
    2429             :   // purpose is to compute bits we don't care about.
    2430       18157 :   if (SimplifyDemandedInstructionBits(I))
    2431             :     return &I;
    2432             : 
    2433       18109 :   if (Value *V = SimplifyBSwap(I))
    2434           3 :     return replaceInstUsesWith(I, V);
    2435             : 
    2436             :   // Is this a 'not' (~) fed by a binary operator?
    2437             :   BinaryOperator *NotOp;
    2438       54318 :   if (match(&I, m_Not(m_BinOp(NotOp)))) {
    2439        4361 :     if (NotOp->getOpcode() == Instruction::And ||
    2440        2854 :         NotOp->getOpcode() == Instruction::Or) {
    2441             :       // ~(~X & Y) --> (X | ~Y) - De Morgan's Law
    2442             :       // ~(~X | Y) === (X & ~Y) - De Morgan's Law
    2443        1010 :       if (dyn_castNotVal(NotOp->getOperand(1)))
    2444           9 :         NotOp->swapOperands();
    2445        1010 :       if (Value *Op0NotVal = dyn_castNotVal(NotOp->getOperand(0))) {
    2446          28 :         Value *NotY = Builder->CreateNot(
    2447          56 :             NotOp->getOperand(1), NotOp->getOperand(1)->getName() + ".not");
    2448          28 :         if (NotOp->getOpcode() == Instruction::And)
    2449          22 :           return BinaryOperator::CreateOr(Op0NotVal, NotY);
    2450           6 :         return BinaryOperator::CreateAnd(Op0NotVal, NotY);
    2451             :       }
    2452             : 
    2453             :       // ~(X & Y) --> (~X | ~Y) - De Morgan's Law
    2454             :       // ~(X | Y) === (~X & ~Y) - De Morgan's Law
    2455        1473 :       if (IsFreeToInvert(NotOp->getOperand(0),
    2456        1967 :                          NotOp->getOperand(0)->hasOneUse()) &&
    2457           6 :           IsFreeToInvert(NotOp->getOperand(1),
    2458           9 :                          NotOp->getOperand(1)->hasOneUse())) {
    2459           6 :         Value *NotX = Builder->CreateNot(NotOp->getOperand(0), "notlhs");
    2460           6 :         Value *NotY = Builder->CreateNot(NotOp->getOperand(1), "notrhs");
    2461           6 :         if (NotOp->getOpcode() == Instruction::And)
    2462           2 :           return BinaryOperator::CreateOr(NotX, NotY);
    2463           4 :         return BinaryOperator::CreateAnd(NotX, NotY);
    2464             :       }
    2465        1924 :     } else if (NotOp->getOpcode() == Instruction::AShr) {
    2466             :       // ~(~X >>s Y) --> (X >>s Y)
    2467         314 :       if (Value *Op0NotVal = dyn_castNotVal(NotOp->getOperand(0)))
    2468           6 :         return BinaryOperator::CreateAShr(Op0NotVal, NotOp->getOperand(1));
    2469             :     }
    2470             :   }
    2471             : 
    2472             :   // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B
    2473             :   ICmpInst::Predicate Pred;
    2474       73430 :   if (match(Op0, m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))) &&
    2475        2164 :       match(Op1, m_AllOnes())) {
    2476        2967 :     cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
    2477         989 :     return replaceInstUsesWith(I, Op0);
    2478             :   }
    2479             : 
    2480       34196 :   if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) {
    2481             :     // fold (xor(zext(cmp)), 1) and (xor(sext(cmp)), -1) to ext(!cmp).
    2482       23514 :     if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) {
    2483        2292 :       if (CmpInst *CI = dyn_cast<CmpInst>(Op0C->getOperand(0))) {
    2484          17 :         if (CI->hasOneUse() && Op0C->hasOneUse()) {
    2485           3 :           Instruction::CastOps Opcode = Op0C->getOpcode();
    2486           6 :           if ((Opcode == Instruction::ZExt || Opcode == Instruction::SExt) &&
    2487           6 :               (RHSC == ConstantExpr::getCast(Opcode, Builder->getTrue(),
    2488             :                                             Op0C->getDestTy()))) {
    2489           6 :             CI->setPredicate(CI->getInversePredicate());
    2490           3 :             return CastInst::Create(Opcode, CI, Op0C->getType());
    2491             :           }
    2492             :         }
    2493             :       }
    2494             :     }
    2495             : 
    2496       23508 :     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
    2497             :       // ~(c-X) == X-c-1 == X+(-c-1)
    2498        1742 :       if (Op0I->getOpcode() == Instruction::Sub && RHSC->isAllOnesValue())
    2499         124 :         if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
    2500           1 :           Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C);
    2501           3 :           return BinaryOperator::CreateAdd(Op0I->getOperand(1),
    2502           2 :                                            SubOne(NegOp0I0C));
    2503             :         }
    2504             : 
    2505        3482 :       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
    2506         908 :         if (Op0I->getOpcode() == Instruction::Add) {
    2507             :           // ~(X-c) --> (-c-1)-X
    2508          12 :           if (RHSC->isAllOnesValue()) {
    2509          11 :             Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI);
    2510          33 :             return BinaryOperator::CreateSub(SubOne(NegOp0CI),
    2511          11 :                                              Op0I->getOperand(0));
    2512           2 :           } else if (RHSC->getValue().isSignMask()) {
    2513             :             // (X + C) ^ signmask -> (X + C + signmask)
    2514           6 :             Constant *C = Builder->getInt(RHSC->getValue() + Op0CI->getValue());
    2515           3 :             return BinaryOperator::CreateAdd(Op0I->getOperand(0), C);
    2516             : 
    2517             :           }
    2518         896 :         } else if (Op0I->getOpcode() == Instruction::Or) {
    2519             :           // (X|C1)^C2 -> X^(C1|C2) iff X&~C1 == 0
    2520         296 :           if (MaskedValueIsZero(Op0I->getOperand(0), Op0CI->getValue(),
    2521             :                                 0, &I)) {
    2522           6 :             Constant *NewRHS = ConstantExpr::getOr(Op0CI, RHSC);
    2523             :             // Anything in both C1 and C2 is known to be zero, remove it from
    2524             :             // NewRHS.
    2525           6 :             Constant *CommonBits = ConstantExpr::getAnd(Op0CI, RHSC);
    2526           6 :             NewRHS = ConstantExpr::getAnd(NewRHS,
    2527           6 :                                        ConstantExpr::getNot(CommonBits));
    2528           6 :             Worklist.Add(Op0I);
    2529          12 :             I.setOperand(0, Op0I->getOperand(0));
    2530           6 :             I.setOperand(1, NewRHS);
    2531           6 :             return &I;
    2532             :           }
    2533         822 :         } else if (Op0I->getOpcode() == Instruction::LShr) {
    2534             :           // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
    2535             :           // E1 = "X ^ C1"
    2536             :           BinaryOperator *E1;
    2537             :           ConstantInt *C1;
    2538         142 :           if (Op0I->hasOneUse() &&
    2539          43 :               (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) &&
    2540          59 :               E1->getOpcode() == Instruction::Xor &&
    2541           6 :               (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) {
    2542             :             // fold (C1 >> C2) ^ C3
    2543           1 :             ConstantInt *C2 = Op0CI, *C3 = RHSC;
    2544           3 :             APInt FoldConst = C1->getValue().lshr(C2->getValue());
    2545           2 :             FoldConst ^= C3->getValue();
    2546             :             // Prepare the two operands.
    2547           2 :             Value *Opnd0 = Builder->CreateLShr(E1->getOperand(0), C2);
    2548           1 :             Opnd0->takeName(Op0I);
    2549           5 :             cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc());
    2550           1 :             Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst);
    2551             : 
    2552           2 :             return BinaryOperator::CreateXor(Opnd0, FoldVal);
    2553             :           }
    2554             :         }
    2555             :       }
    2556             :     }
    2557             :   }
    2558             : 
    2559       34150 :   if (isa<Constant>(Op1))
    2560       13558 :     if (Instruction *FoldedLogic = foldOpWithConstantIntoOperand(I))
    2561             :       return FoldedLogic;
    2562             : 
    2563             :   {
    2564             :     Value *A, *B;
    2565       85185 :     if (match(Op1, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
    2566           9 :       if (A == Op0) {                                      // A^(A|B) == A^(B|A)
    2567           0 :         cast<BinaryOperator>(Op1)->swapOperands();
    2568             :         std::swap(A, B);
    2569             :       }
    2570           9 :       if (B == Op0) {                                      // A^(B|A) == (B|A)^A
    2571           0 :         I.swapOperands();     // Simplified below.
    2572             :         std::swap(Op0, Op1);
    2573             :       }
    2574       85140 :     } else if (match(Op1, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
    2575         106 :       if (A == Op0) {                                      // A^(A&B) -> A^(B&A)
    2576           0 :         cast<BinaryOperator>(Op1)->swapOperands();
    2577             :         std::swap(A, B);
    2578             :       }
    2579         106 :       if (B == Op0) {                                      // A^(B&A) -> (B&A)^A
    2580           0 :         I.swapOperands();     // Simplified below.
    2581             :         std::swap(Op0, Op1);
    2582             :       }
    2583             :     }
    2584             :   }
    2585             : 
    2586             :   {
    2587             :     Value *A, *B;
    2588       85185 :     if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
    2589         549 :       if (A == Op1)                                  // (B|A)^B == (A|B)^B
    2590             :         std::swap(A, B);
    2591         549 :       if (B == Op1)                                  // (A|B)^B == A & ~B
    2592          12 :         return BinaryOperator::CreateAnd(A, Builder->CreateNot(Op1));
    2593       82440 :     } else if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
    2594        1234 :       if (A == Op1)                                        // (A&B)^A -> (B&A)^A
    2595             :         std::swap(A, B);
    2596             :       const APInt *C;
    2597        1803 :       if (B == Op1 &&                                      // (B&A)^A == ~B & A
    2598        1138 :           !match(Op1, m_APInt(C))) {  // Canonical form is (B&C)^C
    2599          18 :         return BinaryOperator::CreateAnd(Builder->CreateNot(A), Op1);
    2600             :       }
    2601             :     }
    2602             :   }
    2603             : 
    2604             :   {
    2605             :     Value *A, *B, *C, *D;
    2606             :     // (A ^ C)^(A | B) -> ((~A) & B) ^ C
    2607       85866 :     if (match(Op0, m_Xor(m_Value(D), m_Value(C))) &&
    2608        2924 :         match(Op1, m_Or(m_Value(A), m_Value(B)))) {
    2609           1 :       if (D == A)
    2610           6 :         return BinaryOperator::CreateXor(
    2611           3 :             Builder->CreateAnd(Builder->CreateNot(A), B), C);
    2612           0 :       if (D == B)
    2613           0 :         return BinaryOperator::CreateXor(
    2614           0 :             Builder->CreateAnd(Builder->CreateNot(B), A), C);
    2615             :     }
    2616             :     // (A | B)^(A ^ C) -> ((~A) & B) ^ C
    2617       85680 :     if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
    2618        2200 :         match(Op1, m_Xor(m_Value(D), m_Value(C)))) {
    2619           7 :       if (D == A)
    2620          18 :         return BinaryOperator::CreateXor(
    2621           9 :             Builder->CreateAnd(Builder->CreateNot(A), B), C);
    2622           4 :       if (D == B)
    2623           0 :         return BinaryOperator::CreateXor(
    2624           0 :             Builder->CreateAnd(Builder->CreateNot(B), A), C);
    2625             :     }
    2626             :     // (A & B) ^ (A ^ B) -> (A | B)
    2627       86409 :     if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
    2628        6470 :         match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
    2629           4 :       return BinaryOperator::CreateOr(A, B);
    2630             :     // (A ^ B) ^ (A & B) -> (A | B)
    2631       85835 :     if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
    2632        3650 :         match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
    2633           4 :       return BinaryOperator::CreateOr(A, B);
    2634             :   }
    2635             : 
    2636             :   // (A & ~B) ^ ~A -> ~(A & B)
    2637             :   // (~B & A) ^ ~A -> ~(A & B)
    2638             :   Value *A, *B;
    2639      102125 :   if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
    2640          44 :       match(Op1, m_Not(m_Specific(A))))
    2641           8 :     return BinaryOperator::CreateNot(Builder->CreateAnd(A, B));
    2642             : 
    2643             :   // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
    2644       34030 :   if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
    2645        1508 :     if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
    2646        1062 :       if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
    2647        1063 :         if (LHS->getOperand(0) == RHS->getOperand(1) &&
    2648           3 :             LHS->getOperand(1) == RHS->getOperand(0))
    2649           1 :           LHS->swapOperands();
    2650        1069 :         if (LHS->getOperand(0) == RHS->getOperand(0) &&
    2651          21 :             LHS->getOperand(1) == RHS->getOperand(1)) {
    2652           6 :           Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
    2653           2 :           unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
    2654           6 :           bool isSigned = LHS->isSigned() || RHS->isSigned();
    2655           2 :           return replaceInstUsesWith(I,
    2656             :                                getNewICmpValue(isSigned, Code, Op0, Op1,
    2657           2 :                                                Builder));
    2658             :         }
    2659             :       }
    2660             : 
    2661       17013 :   if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
    2662             :     return CastedXor;
    2663             : 
    2664       16960 :   return Changed ? &I : nullptr;
    2665             : }

Generated by: LCOV version 1.13