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);
 
@@ -1793,34 +1851,28 @@
       Value *Or = cast<BinaryOperator>(X)->getOperand(0);
       return BinaryOperator::CreateNot(Builder.CreateAnd(Or, Y));
     }
-  }
 
-  // Same version of the LHS which is not demorganed if any subexpressions are
-  // used multiple times, thus match it in this form:
-  // (~A & ~B & C)  | ... --> ...
-  // (~A | ~B | C)  | ... --> ...
-  // TODO: Generalize it to work with all patterns in the above block instead
-  //       of a separate pattern here.
-  if (Op0->hasOneUse() &&
-      (match(Op0,
-             m_c_BinOp(FlippedOpcode,
-                       m_c_BinOp(FlippedOpcode, m_Value(C), m_Not(m_Value(B))),
-                       m_Not(m_Value(A)))) ||
-       match(Op0, m_c_BinOp(FlippedOpcode,
-                            m_c_BinOp(FlippedOpcode, m_Not(m_Value(A)),
-                                      m_Not(m_Value(B))),
-                            m_Value(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)
+
     // (~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)))))
+     if ((Op0->hasOneUse() || X) &&
+         (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)))))) {
+      if (X)
+        return replaceInstUsesWith(I, X);
+
       return BinaryOperator::CreateNot(Builder.CreateBinOp(Opcode, A, B));
+    }
   }
 
   // (~A & B & C) | ... --> ...
@@ -1900,7 +1952,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
@@ -2677,7 +2729,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
@@ -3834,18 +5558,13 @@
 
 define i32 @not_and_not_and_or_not_or_or_commute8(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_not_and_or_not_or_or_commute8(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[TMP2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
 ; CHECK-NEXT:    call void @use(i32 [[NOTB]])
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %a
@@ -3862,18 +5581,13 @@
 
 define i32 @not_and_not_and_or_not_or_or_commute9(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_not_and_or_not_or_or_commute9(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[TMP2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
 ; CHECK-NEXT:    call void @use(i32 [[NOTB]])
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %a
@@ -4222,17 +5936,13 @@
 
 define i32 @not_or_not_or_and_not_and_and_commute8(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_not_or_and_not_and_and_commute8(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[TMP2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
 ; CHECK-NEXT:    call void @use(i32 [[NOTB]])
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %a
@@ -4249,17 +5959,13 @@
 
 define i32 @not_or_not_or_and_not_and_and_commute9(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_not_or_and_not_and_and_commute9(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[TMP2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
 ; CHECK-NEXT:    call void @use(i32 [[NOTB]])
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %a
@@ -4412,3 +6118,295 @@
   call void @use(i32 %not1)
   ret i32 %and4
 }
+
+; (~(a | b) & c) | ~(a | (b | c)) -> ~(a | b)
+; (~(a | b) & c) | ~(b | (a | c)) -> ~(a | b)
+
+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:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %or1 = or i32 %b, %c
+  %or2 = or i32 %or1, %a
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %b, %a
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %not2, %c
+  %or4 = or i32 %and2, %not1
+  ret i32 %or4
+}
+
+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:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %or1 = or i32 %a, %c
+  %or2 = or i32 %or1, %b
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %b, %a
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %not2, %c
+  %or4 = or i32 %and2, %not1
+  ret i32 %or4
+}
+
+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:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %or1 = or i32 %c, %b
+  %or2 = or i32 %or1, %a
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %b, %a
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %not2, %c
+  %or4 = or i32 %and2, %not1
+  ret i32 %or4
+}
+
+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:    [[OR3:%.*]] = or i32 [[A]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
+  %or1 = or i32 %b, %c
+  %or2 = or i32 %a, %or1
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %a, %b
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %not2, %c
+  %or4 = or i32 %and2, %not1
+  ret i32 %or4
+}
+
+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:    [[OR3:%.*]] = or i32 [[B]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
+  %or1 = or i32 %a, %c
+  %or2 = or i32 %b, %or1
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %b, %a
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %not2, %c
+  %or4 = or i32 %and2, %not1
+  ret i32 %or4
+}
+
+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:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
+  %or1 = or i32 %c, %a
+  %or2 = or i32 %or1, %b
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %b, %a
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %c, %not2
+  %or4 = or i32 %and2, %not1
+  ret i32 %or4
+}
+
+define i32 @not_or_and_or_not_or_or_use1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_and_or_not_or_or_use1(
+; 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:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %or1 = or i32 %b, %c
+  %or2 = or i32 %or1, %a
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %b, %a
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %not2, %c
+  %or4 = or i32 %and2, %not1
+  call void @use(i32 %not1)
+  ret i32 %or4
+}
+
+define i32 @not_or_and_or_not_or_or_use2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_and_or_not_or_or_use2(
+; 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:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %or1 = or i32 %a, %c
+  %or2 = or i32 %or1, %b
+  %not1 = xor i32 %or2, -1
+  %or3 = or i32 %b, %a
+  %not2 = xor i32 %or3, -1
+  %and2 = and i32 %not2, %c
+  %or4 = or i32 %and2, %not1
+  call void @use(i32 %not1)
+  ret i32 %or4
+}
+
+; (~(a & b) | c) & ~(a & (b & c)) -> ~(a & b)
+; (~(a & b) | c) & ~(b & (a & c)) -> ~(a & b)
+
+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:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %and1 = and i32 %b, %c
+  %and2 = and i32 %and1, %a
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %b, %a
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %not2, %c
+  %and4 = and i32 %or2, %not1
+  ret i32 %and4
+}
+
+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:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %and1 = and i32 %a, %c
+  %and2 = and i32 %and1, %b
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %b, %a
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %not2, %c
+  %and4 = and i32 %or2, %not1
+  ret i32 %and4
+}
+
+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:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %and1 = and i32 %c, %b
+  %and2 = and i32 %and1, %a
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %b, %a
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %not2, %c
+  %and4 = and i32 %or2, %not1
+  ret i32 %and4
+}
+
+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:    [[AND3:%.*]] = and i32 [[A]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
+  %and1 = and i32 %b, %c
+  %and2 = and i32 %a, %and1
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %a, %b
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %not2, %c
+  %and4 = and i32 %or2, %not1
+  ret i32 %and4
+}
+
+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:    [[AND3:%.*]] = and i32 [[B]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
+  %and1 = and i32 %a, %c
+  %and2 = and i32 %b, %and1
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %b, %a
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %not2, %c
+  %and4 = and i32 %or2, %not1
+  ret i32 %and4
+}
+
+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:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
+  %and1 = and i32 %c, %a
+  %and2 = and i32 %and1, %b
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %b, %a
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %c, %not2
+  %and4 = and i32 %or2, %not1
+  ret i32 %and4
+}
+
+define i32 @not_and_or_and_not_and_and_use1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_or_and_not_and_and_use1(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %and1 = and i32 %b, %c
+  %and2 = and i32 %and1, %a
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %b, %a
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %not2, %c
+  %and4 = and i32 %or2, %not1
+  call void @use(i32 %not1)
+  ret i32 %and4
+}
+
+define i32 @not_and_or_and_not_and_and_use2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_or_and_not_and_and_use2(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    ret i32 [[NOT2]]
+;
+  %and1 = and i32 %a, %c
+  %and2 = and i32 %and1, %b
+  %not1 = xor i32 %and2, -1
+  %and3 = and i32 %b, %a
+  %not2 = xor i32 %and3, -1
+  %or2 = or i32 %not2, %c
+  %and4 = and i32 %or2, %not1
+  call void @use(i32 %not1)
+  ret i32 %and4
+}