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

Generated by: LCOV version 1.13