Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -606,18 +606,12 @@
 
 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
 /// into a single (icmp(A & X) ==/!= Y).
-static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
-                                     llvm::InstCombiner::BuilderTy &Builder) {
-  Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
-  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
-  Optional<std::pair<unsigned, unsigned>> MaskPair =
-      getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
-  if (!MaskPair)
-    return nullptr;
-  assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) &&
-         "Expected equality predicates for masked type of icmps.");
-  unsigned LHSMask = MaskPair->first;
-  unsigned RHSMask = MaskPair->second;
+static Value *foldLogOpOfMaskedICmpsSimple(
+    ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
+    Value *A, Value *B, Value *C, Value *D, Value *E,
+    ICmpInst::Predicate PredL, ICmpInst::Predicate PredR,
+    unsigned LHSMask, unsigned RHSMask,
+    llvm::InstCombiner::BuilderTy &Builder) {
   unsigned Mask = LHSMask & RHSMask;
   if (Mask == 0) {
     // Even if the two sides don't share a common pattern, check if folding can
@@ -748,6 +742,89 @@
   return nullptr;
 }
 
+/// Fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
+/// into (icmp((xor A, Z) & X) ==/!= 0)
+static Value *foldLogOpOfMaskedICmpsXorMask(
+    ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
+    Value *A, ConstantInt *BCst, ConstantInt *CCst,
+    ConstantInt *DCst, ConstantInt *ECst,
+    ICmpInst::Predicate PredL, ICmpInst::Predicate PredR,
+    llvm::InstCombiner::BuilderTy &Builder) {
+  // Use an Xor mask to compare full range against zero
+  // (icmp(A & 4) == 4) && (icmp(A & 3) == 2)
+  // => (icmp((xor A, 6), 7) == 0)
+  // icmp(A & 4) == 4) || (icmp(A & 3) == 2)
+  // => (icmp((xor A, 1), 7) != 0)
+  APInt BAndD = BCst->getValue() & DCst->getValue();
+  Value *X = ConstantExpr::getOr(BCst, DCst);
+  APInt Z = APInt(), B = BCst->getValue(), C = CCst->getValue(),
+    D = DCst->getValue(), E = ECst->getValue();
+  bool LIsEq = (PredL == ICmpInst::ICMP_EQ);
+  bool RIsEq = (PredR == ICmpInst::ICMP_EQ);
+
+  // We have already tested for contradictions in the B & D overlap
+  Z |= LIsEq ? C & B : ~(C & B);
+  Z |= RIsEq ? E & D : ~(E & D);
+
+  if (!IsAnd)
+    Z ^= BAndD;
+
+  Value *NewXor = Builder.CreateXor(A, ConstantInt::get(A->getContext(), Z));
+  Value *NewAnd = Builder.CreateAnd(X, NewXor);
+  return Builder.CreateICmp(IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
+    A, NewAnd);
+}
+
+/// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
+/// into a single (icmp(A & X) ==/!= Y).
+/// or into (icmp((xor A, Z) & X) ==/!= Y)
+static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
+                                     llvm::InstCombiner::BuilderTy &Builder) {
+  Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
+  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
+  Optional<std::pair<unsigned, unsigned>> MaskPair =
+      getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
+  if (!MaskPair)
+    return nullptr;
+  assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) &&
+         "Expected equality predicates for masked type of icmps.");
+  unsigned LHSMask = MaskPair->first;
+  unsigned RHSMask = MaskPair->second;
+
+  // B, C, D, and E must be constants for this optimization
+  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
+  if (!BCst)
+    return nullptr;
+  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
+  if (!CCst)
+    return nullptr;
+  ConstantInt *DCst = dyn_cast<ConstantInt>(D);
+  if (!DCst)
+    return nullptr;
+  ConstantInt *ECst = dyn_cast<ConstantInt>(E);
+  if (!ECst)
+    return nullptr;
+
+  // If B and D intersect, ie. (B & D) != 0, test if they contradict each other
+  // and if so simplify to false (or true if this is an Or).
+  // For example,
+  // (icmp (A & 14), 2) and (icmp (A & 3), 1) -> false.
+  APInt Intersection = BCst->getValue() & DCst->getValue();
+  if (Intersection != 0 &&
+    ((Intersection & CCst->getValue()) != (Intersection & ECst->getValue())))
+      return ConstantInt::get(LHS->getType(), !IsAnd);
+
+  // => (icmp(A & X) ==/!= Y)
+  if (Value *V = foldLogOpOfMaskedICmpsSimple(
+          LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask,
+          Builder))
+    return V;
+
+  // => (icmp((xor A, Z) & X) ==/!= 0)
+  return foldLogOpOfMaskedICmpsXorMask(
+          LHS, RHS, IsAnd, A, BCst, CCst, DCst, ECst, PredL, PredR, Builder);
+}
+
 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
 /// If \p Inverted is true then the check is for the inverted range, e.g.
Index: test/Transforms/InstSimplify/AndOrXor.ll
===================================================================
--- test/Transforms/InstSimplify/AndOrXor.ll
+++ test/Transforms/InstSimplify/AndOrXor.ll
@@ -1132,3 +1132,17 @@
   %tmp5 = and <2 x i32> %tmp4, <i32 4294901761, i32 4294901761> ; mask with 0xFFFF0001
   ret <2 x i32> %tmp5
 }
+
+define i1 @icmp_set_and_unset_bits(i32 %a) {
+; CHECK-LABEL: @icmp_set_and_unset_bits(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 5
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 4
+; CHECK-NEXT:    ret i1 [[TMP2]]
+;
+  %tmp1 = and i32 %a, 1
+  %tmp2 = icmp eq i32 %tmp1, 0
+  %tmp3 = and i32 %a, 4
+  %tmp4 = icmp ne i32 %tmp3, 0
+  %tmp5 = and i1 %tmp2, %tmp4
+  ret i1 %tmp5
+}