Index: llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1717,8 +1717,7 @@
 
 /// Try folding relatively complex patterns for both And and Or operations
 /// with all And and Or swapped.
-static Instruction *foldComplexAndOrPatterns(BinaryOperator &I,
-                                             InstCombiner::BuilderTy &Builder) {
+Instruction *InstCombinerImpl::foldComplexAndOrPatterns(BinaryOperator &I) {
   const Instruction::BinaryOps Opcode = I.getOpcode();
   assert(Opcode == Instruction::And || Opcode == Instruction::Or);
 
@@ -1800,6 +1799,18 @@
             Xor, Builder.CreateNot(Builder.CreateOr(A, C)));
       }
     }
+
+    // (~(A | B) & C) | ~(A | (B | C)) --> ~(A | B)
+    // (~(A | B) & C) | ~(B | (A | C)) --> ~(A | B)
+    // (~(A & B) | C) & ~(A & (B & C)) --> ~(A & B)
+    // (~(A & B) | C) & ~(B & (A & C)) --> ~(A & B)
+    if (match(Op1, m_Not(m_c_BinOp(
+                       Opcode, m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)),
+                       m_Specific(A)))) ||
+        match(Op1, m_Not(m_c_BinOp(
+                       Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)),
+                       m_Specific(B)))))
+      return replaceInstUsesWith(I, X);
   }
 
   return nullptr;
@@ -1830,7 +1841,7 @@
   if (Instruction *Xor = foldAndToXor(I, Builder))
     return Xor;
 
-  if (Instruction *X = foldComplexAndOrPatterns(I, Builder))
+  if (Instruction *X = foldComplexAndOrPatterns(I))
     return X;
 
   // (A|B)&(A|C) -> A|(B&C) etc
@@ -2589,7 +2600,7 @@
   if (Instruction *Xor = foldOrToXor(I, Builder))
     return Xor;
 
-  if (Instruction *X = foldComplexAndOrPatterns(I, Builder))
+  if (Instruction *X = foldComplexAndOrPatterns(I))
     return X;
 
   // (A&B)|(A&C) -> A&(B|C) etc
Index: llvm/lib/Transforms/InstCombine/InstCombineInternal.h
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -371,6 +371,10 @@
   Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
                                                  bool IsAnd);
 
+  /// Try folding relatively complex patterns for both And and Or operations
+  /// with all And and Or swapped.
+  Instruction *foldComplexAndOrPatterns(BinaryOperator &I);
+
 public:
   /// Inserts an instruction \p New before instruction \p Old
   ///
Index: llvm/test/Transforms/InstCombine/and-xor-or.ll
===================================================================
--- llvm/test/Transforms/InstCombine/and-xor-or.ll
+++ llvm/test/Transforms/InstCombine/and-xor-or.ll
@@ -3753,14 +3753,9 @@
 
 define i32 @not_or_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %a
@@ -3774,14 +3769,9 @@
 
 define i32 @not_or_and_or_not_or_or_commute1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute1(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %a, %c
   %or2 = or i32 %or1, %b
@@ -3795,14 +3785,9 @@
 
 define i32 @not_or_and_or_not_or_or_commute2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute2(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %c, %b
   %or2 = or i32 %or1, %a
@@ -3817,14 +3802,9 @@
 define i32 @not_or_and_or_not_or_or_commute3(i32 %a0, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute3(
 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[OR1]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[A]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
   %or1 = or i32 %b, %c
@@ -3840,14 +3820,9 @@
 define i32 @not_or_and_or_not_or_or_commute4(i32 %a, i32 %b0, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute4(
 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[B]], [[OR1]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
   %or1 = or i32 %a, %c
@@ -3862,15 +3837,9 @@
 
 define i32 @not_or_and_or_not_or_or_commute5(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute5(
-; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[C]], [[NOT2]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %or1 = or i32 %c, %a
@@ -3890,10 +3859,8 @@
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %a
@@ -3913,10 +3880,8 @@
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %a, %c
   %or2 = or i32 %or1, %b
@@ -3934,13 +3899,9 @@
 
 define i32 @not_and_or_and_not_and_and(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %a
@@ -3954,13 +3915,9 @@
 
 define i32 @not_and_or_and_not_and_and_commute1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute1(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %a, %c
   %and2 = and i32 %and1, %b
@@ -3974,13 +3931,9 @@
 
 define i32 @not_and_or_and_not_and_and_commute2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute2(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %c, %b
   %and2 = and i32 %and1, %a
@@ -3995,13 +3948,9 @@
 define i32 @not_and_or_and_not_and_and_commute3(i32 %a0, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute3(
 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[AND1]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[A]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
   %and1 = and i32 %b, %c
@@ -4017,13 +3966,9 @@
 define i32 @not_and_or_and_not_and_and_commute4(i32 %a, i32 %b0, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute4(
 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[B]], [[AND1]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
   %and1 = and i32 %a, %c
@@ -4038,14 +3983,9 @@
 
 define i32 @not_and_or_and_not_and_and_commute5(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute5(
-; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[C]], [[NOT2]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %and1 = and i32 %c, %a
@@ -4065,10 +4005,8 @@
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %a
@@ -4088,10 +4026,8 @@
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %a, %c
   %and2 = and i32 %and1, %b