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

Generated by: LCOV version 1.13