Index: llvm/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/lib/Analysis/ValueTracking.cpp
+++ llvm/lib/Analysis/ValueTracking.cpp
@@ -270,6 +270,12 @@
   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;
+
+  // Look for a pattern:(A & ~B) op B
+  if (match(LHS, m_c_And(m_Not(m_Specific(RHS)), m_Value())) ||
+      match(RHS, m_c_And(m_Not(m_Specific(LHS)), m_Value())))
+    return true;
+
   IntegerType *IT = cast<IntegerType>(LHS->getType()->getScalarType());
   KnownBits LHSKnown(IT->getBitWidth());
   KnownBits RHSKnown(IT->getBitWidth());
Index: llvm/test/Analysis/ValueTracking/known-non-common-bits.ll
===================================================================
--- /dev/null
+++ llvm/test/Analysis/ValueTracking/known-non-common-bits.ll
@@ -0,0 +1,90 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define i32 @_Z11and_to_xor1ii(i32 %A, i32 %B) {
+; CHECK-LABEL: @_Z11and_to_xor1ii(
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+  %NOT_B = xor i32 %B, -1            ; %NOT_B = ~B
+  %AND = and i32 %NOT_B, %A          ; %AND = ~B & A
+  %RET = add nsw i32 %AND, %B        ; (~B & A) + B
+  ret i32 %RET
+}
+
+define i32 @_Z11and_to_xor2ii(i32 %A, i32 %B) {
+; CHECK-LABEL: @_Z11and_to_xor2ii(
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+  %NOT_B = xor i32 %B, -1            ; %NOT_B = ~B
+  %AND = and i32 %NOT_B, %A          ; %AND = ~B & A
+  %RET = add nsw i32 %B, %AND        ; B + (~B & A)
+  ret i32 %RET
+}
+
+define i32 @_Z11and_to_xor3ii(i32 %A, i32 %B) {
+; CHECK-LABEL: @_Z11and_to_xor3ii(
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+  %NOT_B = xor i32 %B, -1            ; %NOT_B = ~B
+  %AND = and i32 %A, %NOT_B          ; %AND = A & ~B
+  %RET = add nsw i32 %AND, %B        ; (A & ~B) + B
+  ret i32 %RET
+}
+
+define i32 @_Z11and_to_xor4ii(i32 %A, i32 %B) {
+; CHECK-LABEL: @_Z11and_to_xor4ii(
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+  %NOT_B = xor i32 %B, -1            ; %NOT_B = ~B
+  %AND = and i32 %A, %NOT_B          ; %AND = A & ~B
+  %RET = add nsw i32 %B, %AND        ; B + (A & ~B)
+  ret i32 %RET
+}
+
+define <2 x i32> @_Z11and_to_xor1vv(<2 x i32> %A, <2 x i32> %B) {
+; CHECK-LABEL: @_Z11and_to_xor1vv(
+; CHECK-NEXT:    [[RET:%.*]] = or <2 x i32> [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[RET]]
+;
+  %NOT_B = xor <2 x i32> %B, <i32 -1, i32 -1>            ; %NOT_B = ~B
+  %AND = and <2 x i32> %NOT_B, %A                        ; %AND = ~B & A
+  %RET = add nsw <2 x i32> %AND, %B                       ; (~B & A) + B
+  ret <2 x i32> %RET
+}
+
+define <2 x i32> @_Z11and_to_xor2vv(<2 x i32> %A, <2 x i32> %B) {
+; CHECK-LABEL: @_Z11and_to_xor2vv(
+; CHECK-NEXT:    [[RET:%.*]] = or <2 x i32> [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[RET]]
+;
+  %NOT_B = xor <2 x i32> %B, <i32 -1, i32 -1>            ; %NOT_B = ~B
+  %AND = and <2 x i32> %NOT_B, %A                        ; %AND = ~B & A
+  %RET = add nsw <2 x i32> %B, %AND                      ; B + (~B & A)
+  ret <2 x i32> %RET
+}
+
+define <2 x i32> @_Z11and_to_xor3vv(<2 x i32> %A, <2 x i32> %B) {
+; CHECK-LABEL: @_Z11and_to_xor3vv(
+; CHECK-NEXT:    [[RET:%.*]] = or <2 x i32> [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[RET]]
+;
+  %NOT_B = xor <2 x i32> %B, <i32 -1, i32 -1>            ; %NOT_B = ~B
+  %AND = and <2 x i32> %A, %NOT_B                        ; %AND = A & ~B
+  %RET = add nsw <2 x i32> %AND, %B                       ; (A & ~B) + B
+  ret <2 x i32> %RET
+}
+
+define <2 x i32> @_Z11and_to_xor4vv(<2 x i32> %A, <2 x i32> %B) {
+; CHECK-LABEL: @_Z11and_to_xor4vv(
+; CHECK-NEXT:    [[RET:%.*]] = or <2 x i32> [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[RET]]
+;
+  %NOT_B = xor <2 x i32> %B, <i32 -1, i32 -1>            ; %NOT_B = ~B
+  %AND = and <2 x i32> %A, %NOT_B                        ; %AND = A & ~B
+  %RET = add nsw <2 x i32> %B, %AND                      ; B + (A & ~B)
+  ret <2 x i32> %RET
+}