[InstCombine] (~a & b & c) | ~(a | b | c) -> ~(a | (b ^ c))

[rampitec]

Summary

Transform

(~a & b & c) | ~(a | b | c) -> ~(a | (b ^ c))

And swapped case:

(~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)

----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
  %or1 = or i4 %b, %a
  %or2 = or i4 %or1, %c
  %not1 = xor i4 %or2, 15
  %not2 = xor i4 %a, 15
  %and1 = and i4 %b, %not2
  %and2 = and i4 %and1, %c
  %or3 = or i4 %and2, %not1
  ret i4 %or3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
  %1 = xor i4 %c, %b
  %2 = or i4 %1, %a
  %or3 = xor i4 %2, 15
  ret i4 %or3
}
Transformation seems to be correct!

----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
  %and1 = and i4 %b, %a
  %and2 = and i4 %and1, %c
  %not1 = xor i4 %and2, 15
  %not2 = xor i4 %a, 15
  %or1 = or i4 %not2, %b
  %or2 = or i4 %or1, %c
  %and3 = and i4 %or2, %not1
  ret i4 %and3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
  %xor = xor i4 %b, %c
  %not = xor i4 %a, 15
  %or = or i4 %xor, %not
  ret i4 %or
}
Transformation seems to be correct!

[rampitec]

Rebased.

[rampitec]

In the light of D113526 this needs to be rebased and handle inverted pattern:

(~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)

----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
  %and1 = and i4 %b, %a
  %and2 = and i4 %and1, %c
  %not1 = xor i4 %and2, 15
  %not2 = xor i4 %a, 15
  %or1 = or i4 %not2, %b
  %or2 = or i4 %or1, %c
  %and3 = and i4 %or2, %not1
  ret i4 %and3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
  %xor = xor i4 %b, %c
  %not = xor i4 %a, 15
  %or = or i4 %xor, %not
  ret i4 %or
}
Transformation seems to be correct!

[rampitec]

Rebased and added swapped case:

(~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)

[rampitec]

Capture ~A from the original expression to reuse.

[rampitec]

Rebased.

[rampitec]

Rebased.

[rampitec]

Ping.

[spatel]

LGTM - admittedly, I didn't try to line up all of the possible patterns with the tests because there are so many combinations.
So this is at the limit of what we can do in instcombine pattern-matching, but I don't see any way to reduce the complexity.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1807–1808

Comment seems truncated from the similar code comment above here.

[rampitec]

Updated comment.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Op0->hasOneUse() &&
         // Y = A ^ B
         Value *Xor = Builder.CreateXor(Y, C);
         return BinaryOperator::CreateOr(
             Xor, Builder.CreateNot(Builder.CreateOr(A, C)));
       }
     }
   }
 
+  // (~A & B & C) | ~(A | B | C) -> ~(A | (B ^ C))
+  // (~A | B | C) & ~(A & B & C) -> (~A | (B ^ C))
+  // TODO: One use checks are conservative. We just need to check that a total
+  //       number of multiple used values.
+  if (match(Op0,
+            m_OneUse(m_c_BinOp(FlippedOpcode,
+                               m_BinOp(FlippedOpcode, m_Value(B), m_Value(C)),
+                               m_CombineAnd(m_Value(X), m_Not(m_Value(A)))))) ||
+      match(Op0, m_OneUse(m_c_BinOp(
+                     FlippedOpcode,
+                     m_c_BinOp(FlippedOpcode, m_Value(C),
+                               m_CombineAnd(m_Value(X), m_Not(m_Value(A)))),
+                     m_Value(B))))) {
+    // X = ~A
+    if (match(Op1, m_OneUse(m_Not(m_c_BinOp(
+                       Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)),
+                       m_Specific(C))))) ||
+        match(Op1, m_OneUse(m_Not(m_c_BinOp(
+                       Opcode, m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)),
+                       m_Specific(A))))) ||
+        match(Op1, m_OneUse(m_Not(m_c_BinOp(
+                       Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)),
+                       m_Specific(B)))))) {
+      Value *Xor = Builder.CreateXor(B, C);
+      return (Opcode == Instruction::Or)
+                 ? BinaryOperator::CreateNot(Builder.CreateOr(Xor, A))
+                 : BinaryOperator::CreateOr(Xor, X);
+    }
+  }
+
   return nullptr;
 }
 
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
 Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
   Type *Ty = I.getType();

llvm/test/Transforms/InstCombine/and-xor-or.ll

;
   call void @use(i32 %not2)
   ret i32 %and3
 }
 
 ; (~a & b & c) | ~(a | b | c) -> ~(a | (b ^ c))
 
 define i32 @not_and_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute1_or(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute1_or(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[C:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %c, %a
   %or2 = or i32 %or1, %b
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute2_or(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute2_or(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %a
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute1_and(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute1_and(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %c
   %and2 = and i32 %and1, %b
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute2_and(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute2_and(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[C]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[NOT2]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %not2
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute1(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %a, %b
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute2(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute2(
 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[C]], [[OR1]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %or1 = or i32 %b, %a
   %or2 = or i32 %c, %or1
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute3(i32 %a, i32 %b0, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute3(
 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[NOT2]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %b, %not2
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_commute4(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_commute4(
 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[C]], [[AND1]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %c, %and1
   %or3 = or i32 %and2, %not1
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_use1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_use1(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   call void @use(i32 %or1)
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_use2(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
;
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   call void @use(i32 %not1)
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_use4(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_use4(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or3 = or i32 %and2, %not1
   call void @use(i32 %not2)
   ret i32 %or3
 }
 
 define i32 @not_and_and_or_not_or_or_use5(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_use5(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
   %or1 = or i32 %b, %a
   %or2 = or i32 %or1, %c
   %not1 = xor i32 %or2, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
;
   call void @use(i32 %and2)
   ret i32 %or3
 }
 
 ; (~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)
 
 define i32 @not_or_or_and_not_and_and(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute1_and(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute1_and(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[C:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %c, %a
   %and2 = and i32 %and1, %b
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute2_and(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute2_and(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %a
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute1_or(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute1_or(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[B]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %c
   %or2 = or i32 %or1, %b
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute2_or(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute2_or(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[C]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[NOT2]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %not2
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute1(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %a, %b
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute2(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute2(
 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[C]], [[AND1]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %and1 = and i32 %b, %a
   %and2 = and i32 %c, %and1
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute3(i32 %a, i32 %b0, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute3(
 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[NOT2]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %b, %not2
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_commute4(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_commute4(
 ; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[C]], [[OR1]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %c, %or1
   %and3 = and i32 %or2, %not1
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_use1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_use1(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   call void @use(i32 %and1)
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_use2(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
;
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   call void @use(i32 %not1)
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_use4(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_use4(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
   call void @use(i32 %not2)
   ret i32 %and3
 }
 
 define i32 @not_or_or_and_not_and_and_use5(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_use5(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
   %and1 = and i32 %b, %a
   %and2 = and i32 %and1, %c
   %not1 = xor i32 %and2, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b