Index: llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1822,15 +1822,19 @@
 
     // (~(A | B) & C) | ~(A | C) --> ~((B & C) | A)
     // (~(A & B) | C) & ~(A & C) --> ~((B | C) & A)
-    if (X && match(Op1, m_OneUse(m_Not(m_OneUse(
-                            m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
+    // (~A & ~B & C) | ~(A | C) --> ~((B & C) | A)
+    // (~A | ~B | C) & ~(A & C) --> ~((B | C) & A)
+    if (match(Op1, m_OneUse(m_Not(m_OneUse(
+                       m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
       return BinaryOperator::CreateNot(Builder.CreateBinOp(
           Opcode, Builder.CreateBinOp(FlippedOpcode, B, C), A));
 
     // (~(A | B) & C) | ~(B | C) --> ~((A & C) | B)
     // (~(A & B) | C) & ~(B & C) --> ~((A | C) & B)
-    if (X && match(Op1, m_OneUse(m_Not(m_OneUse(
-                            m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)))))))
+    // (~A & ~B & C) | ~(B | C) --> ~((A & C) | B)
+    // (~A | ~B | C) & ~(B & C) --> ~((A | C) & B)
+    if (match(Op1, m_OneUse(m_Not(m_OneUse(
+                       m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)))))))
       return BinaryOperator::CreateNot(Builder.CreateBinOp(
           Opcode, Builder.CreateBinOp(FlippedOpcode, A, C), B));
 
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
@@ -3202,6 +3202,546 @@
   ret i32 %and3
 }
 
+; (b & ~a & ~c) | ~(a | b) --> ~((b & c) | a)
+
+define i32 @and_not_and_and_not_or_not_or(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_commute1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_commute1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTC]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %notc
+  %and2 = and i32 %and1, %nota
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_commute2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_commute2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %nota, %notc
+  %and2 = and i32 %and1, %b
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_commute3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_commute3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %a, %b
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_use1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_use1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_use2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_use2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %or2)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_use3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_use3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOTC]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %or1)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_use4(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_use4(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOTC]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %not1)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_use5(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_use5(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %notc)
+  ret i32 %or2
+}
+
+define i32 @and_not_and_and_not_or_not_or_use6(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_and_and_not_or_not_or_use6(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %b, %nota
+  %and2 = and i32 %and1, %notc
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %or2)
+  call void @use(i32 %notc)
+  ret i32 %or2
+}
+
+; (b | ~a | ~c) & ~(a & b) --> ~((b | c) & a)
+
+define i32 @or_not_or_or_not_and_not_and(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_commute1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_commute1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTC]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %notc
+  %or2 = or i32 %or1, %nota
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_commute2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_commute2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %nota, %notc
+  %or2 = or i32 %or1, %b
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_commute3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_commute3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %a, %b
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_use1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_use1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_use2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_use2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  call void @use(i32 %and2)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_use3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_use3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOTC]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  call void @use(i32 %and1)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_use4(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_use4(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOTC]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  call void @use(i32 %not1)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_use5(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_use5(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  call void @use(i32 %notc)
+  ret i32 %and2
+}
+
+define i32 @or_not_or_or_not_and_not_and_use6(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_or_or_not_and_not_and_use6(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[B:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOTC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[AND2]]
+;
+  %nota = xor i32 %a, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %b, %a
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %b, %nota
+  %or2 = or i32 %or1, %notc
+  %and2 = and i32 %or2, %not1
+  call void @use(i32 %nota)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  call void @use(i32 %and2)
+  call void @use(i32 %notc)
+  ret i32 %and2
+}
+
 ; (a & ~(b | c)) | ~(a | (b ^ c)) --> (~a & b & c) | ~(b | c)
 
 define i32 @and_not_or_or_not_or_xor(i32 %a, i32 %b, i32 %c) {