diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2674,6 +2674,8 @@
   // A | ( A ^ B) -> A |  B
   // A | (~A ^ B) -> A | ~B
   // (A & B) | (A ^ B)
+  // ~A | (A ^ B) -> ~(A & B)
+  // The swap above should always make Op0 the 'not' for the last case.
   if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
     if (Op0 == A || Op0 == B)
       return BinaryOperator::CreateOr(A, B);
@@ -2682,6 +2684,10 @@
         match(Op0, m_And(m_Specific(B), m_Specific(A))))
       return BinaryOperator::CreateOr(A, B);
 
+    if ((Op0->hasOneUse() || Op1->hasOneUse()) &&
+        (match(Op0, m_Not(m_Specific(A))) || match(Op0, m_Not(m_Specific(B)))))
+      return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
+
     if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
       Value *Not = Builder.CreateNot(B, B->getName() + ".not");
       return BinaryOperator::CreateOr(Not, Op0);
diff --git a/llvm/test/Transforms/InstCombine/and-or-icmps.ll b/llvm/test/Transforms/InstCombine/and-or-icmps.ll
--- a/llvm/test/Transforms/InstCombine/and-or-icmps.ll
+++ b/llvm/test/Transforms/InstCombine/and-or-icmps.ll
@@ -369,12 +369,11 @@
 ; CHECK-NEXT:    [[B11:%.*]] = zext i1 [[TMP1]] to i16
 ; CHECK-NEXT:    [[C10:%.*]] = icmp ugt i16 [[L7]], [[B11]]
 ; CHECK-NEXT:    [[C5:%.*]] = icmp slt i16 [[L7]], 1
-; CHECK-NEXT:    [[C11:%.*]] = icmp ne i16 [[L7]], 0
 ; CHECK-NEXT:    [[C7:%.*]] = icmp slt i16 [[L7]], 0
 ; CHECK-NEXT:    [[B15:%.*]] = xor i1 [[C7]], [[C10]]
-; CHECK-NEXT:    [[B19:%.*]] = xor i1 [[C11]], [[B15]]
+; CHECK-NEXT:    [[C6:%.*]] = xor i1 [[B15]], true
 ; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[C10]], [[C5]]
-; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[B19]]
+; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[C6]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[C10]], true
 ; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = sext i1 [[C3]] to i64
diff --git a/llvm/test/Transforms/InstCombine/or-xor.ll b/llvm/test/Transforms/InstCombine/or-xor.ll
--- a/llvm/test/Transforms/InstCombine/or-xor.ll
+++ b/llvm/test/Transforms/InstCombine/or-xor.ll
@@ -63,9 +63,8 @@
 
 define i32 @test5(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i32 [[X]], -1
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %xor = xor i32 %x, %y
@@ -79,9 +78,8 @@
 
 define <2 x i4> @test5_commuted(<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @test5_commuted(
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i4> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor <2 x i4> [[X]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[Z:%.*]] = or <2 x i4> [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor <2 x i4> [[TMP1]], <i4 -1, i4 -1>
 ; CHECK-NEXT:    ret <2 x i4> [[Z]]
 ;
   %xor = xor <2 x i4> %x, %y
@@ -95,9 +93,8 @@
 
 define i64 @test5_commuted_x_y(i64 %x, i64 %y) {
 ; CHECK-LABEL: @test5_commuted_x_y(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i64 [[X]], -1
-; CHECK-NEXT:    [[Z:%.*]] = or i64 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i64 [[TMP1]], -1
 ; CHECK-NEXT:    ret i64 [[Z]]
 ;
   %xor = xor i64 %y, %x
@@ -109,10 +106,10 @@
 
 define i8 @test5_extra_use_not(i8 %x, i8 %y, i8* %dst) {
 ; CHECK-LABEL: @test5_extra_use_not(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X]], -1
+; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    store i8 [[NOTX]], i8* [[DST:%.*]], align 1
-; CHECK-NEXT:    [[Z:%.*]] = or i8 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], [[Y:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i8 [[TMP1]], -1
 ; CHECK-NEXT:    ret i8 [[Z]]
 ;
   %xor = xor i8 %x, %y
@@ -127,8 +124,8 @@
 ; CHECK-LABEL: @test5_extra_use_xor(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i65 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    store i65 [[XOR]], i65* [[DST:%.*]], align 4
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i65 [[X]], -1
-; CHECK-NEXT:    [[Z:%.*]] = or i65 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i65 [[X]], [[Y]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i65 [[TMP1]], -1
 ; CHECK-NEXT:    ret i65 [[Z]]
 ;
   %xor = xor i65 %x, %y