Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -190,6 +190,14 @@
          "LHS and RHS should have the same type");
   assert(LHS->getType()->isIntOrIntVectorTy() &&
          "LHS and RHS should be integers");
+  // Look for an inverted mask: (X & ~M) op (Y & M).
+  Value *M;
+  if (match(LHS, m_c_And(m_Not(m_Value(M)), m_Value())) &&
+      match(RHS, m_c_And(m_Specific(M), m_Value())))
+    return true;
+  if (match(RHS, m_c_And(m_Not(m_Value(M)), m_Value())) &&
+      match(LHS, m_c_And(m_Specific(M), m_Value())))
+    return true;
   IntegerType *IT = cast<IntegerType>(LHS->getType()->getScalarType());
   KnownBits LHSKnown(IT->getBitWidth());
   KnownBits RHSKnown(IT->getBitWidth());
Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2446,6 +2446,10 @@
   if (Value *V = SimplifyBSwap(I, Builder))
     return replaceInstUsesWith(I, V);
 
+  // A^B --> A|B iff A and B have no bits set in common.
+  if (haveNoCommonBitsSet(Op0, Op1, DL, &AC, &I, &DT))
+    return BinaryOperator::CreateOr(Op0, Op1);
+
   // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
   Value *X, *Y;
 
Index: test/Transforms/InstCombine/logical-select.ll
===================================================================
--- test/Transforms/InstCombine/logical-select.ll
+++ test/Transforms/InstCombine/logical-select.ll
@@ -399,11 +399,8 @@
 
 define i1 @bools_multi_uses2(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @bools_multi_uses2(
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[NOT]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[C]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = xor i1 [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret i1 [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i1 [[B:%.*]], i1 [[A:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %not = xor i1 %c, -1
   %and1 = and i1 %not, %a
Index: test/Transforms/InstCombine/masked-merge-add.ll
===================================================================
--- test/Transforms/InstCombine/masked-merge-add.ll
+++ test/Transforms/InstCombine/masked-merge-add.ll
@@ -21,7 +21,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %x, %m
@@ -36,7 +36,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor <2 x i32> [[M]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    [[AND1:%.*]] = and <2 x i32> [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add <2 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or <2 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <2 x i32> [[RET]]
 ;
   %and = and <2 x i32> %x, %m
@@ -51,7 +51,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and <3 x i32> [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor <3 x i32> [[M]], <i32 -1, i32 undef, i32 -1>
 ; CHECK-NEXT:    [[AND1:%.*]] = and <3 x i32> [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add <3 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or <3 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <3 x i32> [[RET]]
 ;
   %and = and <3 x i32> %x, %m
@@ -129,7 +129,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %m, %x ; swapped order
@@ -145,7 +145,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -161,7 +161,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %x, %m
@@ -177,7 +177,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -193,7 +193,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %m, %x ; swapped order
@@ -209,7 +209,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -226,7 +226,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -263,7 +263,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    call void @use32(i32 [[AND]])
 ; CHECK-NEXT:    call void @use32(i32 [[NEG]])
 ; CHECK-NEXT:    call void @use32(i32 [[AND1]])
Index: test/Transforms/InstCombine/masked-merge-xor.ll
===================================================================
--- test/Transforms/InstCombine/masked-merge-xor.ll
+++ test/Transforms/InstCombine/masked-merge-xor.ll
@@ -21,7 +21,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %x, %m
@@ -36,7 +36,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor <2 x i32> [[M]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    [[AND1:%.*]] = and <2 x i32> [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor <2 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or <2 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <2 x i32> [[RET]]
 ;
   %and = and <2 x i32> %x, %m
@@ -51,7 +51,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and <3 x i32> [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor <3 x i32> [[M]], <i32 -1, i32 undef, i32 -1>
 ; CHECK-NEXT:    [[AND1:%.*]] = and <3 x i32> [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor <3 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or <3 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <3 x i32> [[RET]]
 ;
   %and = and <3 x i32> %x, %m
@@ -129,7 +129,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %m, %x ; swapped order
@@ -145,7 +145,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -161,7 +161,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %x, %m
@@ -177,7 +177,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -193,7 +193,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %m, %x ; swapped order
@@ -209,7 +209,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -226,7 +226,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
@@ -263,7 +263,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    call void @use32(i32 [[AND]])
 ; CHECK-NEXT:    call void @use32(i32 [[NEG]])
 ; CHECK-NEXT:    call void @use32(i32 [[AND1]])