diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -282,6 +282,20 @@
         match(LHS, m_c_And(m_Specific(M), m_Value())))
       return true;
   }
+
+  // X op (Y & ~X)
+  if (match(RHS, m_c_And(m_Not(m_Specific(LHS)), m_Value())) ||
+      match(LHS, m_c_And(m_Not(m_Specific(RHS)), m_Value())))
+    return true;
+
+  // X op ((X & Y) ^ Y) -- this is the canonical form of the previous pattern
+  // for constant Y.
+  Value *Y;
+  if (match(RHS,
+            m_c_Xor(m_c_And(m_Specific(LHS), m_Value(Y)), m_Deferred(Y))) ||
+      match(LHS, m_c_Xor(m_c_And(m_Specific(RHS), m_Value(Y)), m_Deferred(Y))))
+    return true;
+
   // Look for: (A & B) op ~(A | B)
   {
     Value *A, *B;
diff --git a/llvm/test/Transforms/InstCombine/add.ll b/llvm/test/Transforms/InstCombine/add.ll
--- a/llvm/test/Transforms/InstCombine/add.ll
+++ b/llvm/test/Transforms/InstCombine/add.ll
@@ -1395,9 +1395,7 @@
 
 define i8 @add_and_xor(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_and_xor(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR]], [[Y:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %xor = xor i8 %x, -1
@@ -1435,9 +1433,7 @@
 define i8 @add_and_xor_commuted1(i8 %x, i8 %_y) {
 ; CHECK-LABEL: @add_and_xor_commuted1(
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[XOR]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
@@ -1450,9 +1446,7 @@
 define i8 @add_and_xor_commuted2(i8 %_x, i8 %y) {
 ; CHECK-LABEL: @add_and_xor_commuted2(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR]], [[Y:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1466,9 +1460,7 @@
 ; CHECK-LABEL: @add_and_xor_commuted3(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[XOR]]
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1485,7 +1477,7 @@
 ; CHECK-NEXT:    call void @use(i8 [[XOR]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %xor = xor i8 %x, -1
@@ -1500,7 +1492,7 @@
 ; CHECK-LABEL: @add_xor_and_const(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], 42
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], 42
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, 42
@@ -1527,7 +1519,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, %y
@@ -1572,7 +1564,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %y, %x
@@ -1588,7 +1580,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
@@ -1605,7 +1597,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
@@ -1622,7 +1614,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1639,7 +1631,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1657,7 +1649,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1676,7 +1668,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1694,7 +1686,7 @@
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
 ; CHECK-NEXT:    call void @use(i8 [[XOR]])
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, %y