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

[rampitec]

Summary

and swapped (~a | ~b | c) & (~a | ~c | b) --> ~((b ^ c) & a).
This is the extension of handled case (~(a | b) & c) | (~(a | c) & b)
--> (b ^ c) & ~a with expression not being demorganed because
of mutiple uses of ~a and/or ~b.

The rest of the cases with the same LHS are guarded to use only
the original demorganed form for now.

[spatel]

This is pushing over the edge of pattern-matching complexity. But again, I don't have any real suggestions for improvement, so adding more potential reviewers.

[foad]

I don't really have an opinion on the patch, but I'm curious.

Given (~a & ~b & c) | (~a & ~c & b), do we make any attempt to pull out the ~a like this: ~a & ((~b & c) | (~c & b)) ? If not, why not? Would that be a good thing to address? Then it's just a case of simplifying the two-variable (~b & c) | (~c & b) -> b ^ c which is easy.

[spatel]

In D116231#3224577, @foad wrote:

I don't really have an opinion on the patch, but I'm curious.

Given (~a & ~b & c) | (~a & ~c & b), do we make any attempt to pull out the ~a like this: ~a & ((~b & c) | (~c & b)) ? If not, why not? Would that be a good thing to address? Then it's just a case of simplifying the two-variable (~b & c) | (~c & b) -> b ^ c which is easy.

InstCombine does try that transform via InstCombinerImpl::SimplifyAssociativeOrCommutative() and/or InstCombinerImpl::SimplifyUsingDistributiveLaws(). And that works as expected - for example if we alter the 1st modified test in this patch to be like this:

define i32 @not_and_not_and_and_or(i32 %a, i32 %b, i32 %c) {
  %nota = xor i32 %a, -1
  %notb = xor i32 %b, -1
  %and1 = and i32 %nota, %c
  %and2 = and i32 %and1, %notb
  %or1 = or i32 %a, %c
  %not1 = xor i32 %or1, -1
  %and3 = and i32 %not1, %b
  %or3 = or i32 %and2, %and3
  call void @use(i32 %nota)
  call void @use(i32 %notb)
  ret i32 %or3

Then it reduces because we find the 'b' and '~b' values directly in the operands of the 'and' instructions. So this might be a question for "-reassociate" - can we get that pass to arrange the operands such that -instcombine can fold this (without breaking some other pattern)?

[rampitec]

In D116231#3225213, @spatel wrote:

In D116231#3224577, @foad wrote:

I don't really have an opinion on the patch, but I'm curious.

Given (~a & ~b & c) | (~a & ~c & b), do we make any attempt to pull out the ~a like this: ~a & ((~b & c) | (~c & b)) ? If not, why not? Would that be a good thing to address? Then it's just a case of simplifying the two-variable (~b & c) | (~c & b) -> b ^ c which is easy.

InstCombine does try that transform via InstCombinerImpl::SimplifyAssociativeOrCommutative() and/or InstCombinerImpl::SimplifyUsingDistributiveLaws(). And that works as expected - for example if we alter the 1st modified test in this patch to be like this:

define i32 @not_and_not_and_and_or(i32 %a, i32 %b, i32 %c) {
  %nota = xor i32 %a, -1
  %notb = xor i32 %b, -1
  %and1 = and i32 %nota, %c
  %and2 = and i32 %and1, %notb
  %or1 = or i32 %a, %c
  %not1 = xor i32 %or1, -1
  %and3 = and i32 %not1, %b
  %or3 = or i32 %and2, %and3
  call void @use(i32 %nota)
  call void @use(i32 %notb)
  ret i32 %or3

Then it reduces because we find the 'b' and '~b' values directly in the operands of the 'and' instructions. So this might be a question for "-reassociate" - can we get that pass to arrange the operands such that -instcombine can fold this (without breaking some other pattern)?

Ressociate does that and in fact a simpler case works. The problem is with a more complex case where other subexpression is used elsewhere. For example if (~a & b) is used. In that case reassociate does not do it because it is not beneficial, and it only becomes beneficial when we consider a bigger pattern.

In fact the original motivating case has all possible subexpression permutations in its 255 logical functions, which then lead to mutlti-use cases.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Instruction *foldComplexAndOrPatterns(BinaryOperator &I,
   const Instruction::BinaryOps Opcode = I.getOpcode();
   assert(Opcode == Instruction::And || Opcode == Instruction::Or);
 
   // Flip the logic operation.
   const Instruction::BinaryOps FlippedOpcode =
       (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
-  Value *A, *B, *C, *X, *Y, *Dummy;
+  Value *A, *B, *C, *X, *Y, *NotA, *NotB, *Dummy;
 
   // Match following expressions:
   // (~(A | B) & C)
   // (~(A & B) | C)
-  // Captures X = ~(A | B) or ~(A & B)
+  // The LHS is not demorganed if any subexpressions are used multiple times,
+  // thus match it in this form too:
+  // (~A & ~B & C)
+  // (~A | ~B | C)
+  // Captures X = ~(A | B) or ~(A & B) for demorganed form.
+  // Captures NotA = ~A and NotB = ~B otherwise.
   const auto matchNotOrAnd =
       [Opcode, FlippedOpcode](Value *Op, auto m_A, auto m_B, auto m_C,
-                              Value *&X, bool CountUses = false) -> bool {
+                              Value *&X, Value *&NotA, Value *&NotB,
+                              bool CountUses = false) -> bool {
     if (CountUses && !Op->hasOneUse())
       return false;
 
+    NotA = nullptr;
+    NotB = nullptr;
     if (match(Op, m_c_BinOp(FlippedOpcode,
                             m_CombineAnd(m_Value(X),
                                          m_Not(m_c_BinOp(Opcode, m_A, m_B))),
                             m_C)))
       return !CountUses || X->hasOneUse();
 
+    X = nullptr;
+    Value *Y;
+    if (match(Op, m_c_BinOp(FlippedOpcode,
+                            m_CombineAnd(m_Value(Y),
+                                         m_c_BinOp(FlippedOpcode, m_C,
+                                                   m_CombineAnd(m_Value(NotB),
+                                                                m_Not(m_B)))),
+                            m_CombineAnd(m_Value(NotA), m_Not(m_A)))) ||
+        match(Op,
+              m_c_BinOp(FlippedOpcode,
+                        m_CombineAnd(
+                            m_Value(Y),
+                            m_c_BinOp(FlippedOpcode,
+                                      m_CombineAnd(m_Value(NotA), m_Not(m_A)),
+                                      m_CombineAnd(m_Value(NotB), m_Not(m_B)))),
+                        m_C)))
+      return !CountUses || Y->hasOneUse();
+
     return false;
   };
 
   // (~(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 does not exceed reduction
   //       in operations.
-  if (matchNotOrAnd(Op0, m_Value(A), m_Value(B), m_Value(C), X)) {
+  if (matchNotOrAnd(Op0, m_Value(A), m_Value(B), m_Value(C), X, NotA, NotB)) {
     // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
     // (~(A & B) | C) & (~(A & C) | B) --> ~((B ^ C) & A)
+    // (~A & ~B & C) | (~(A | C) & B) --> (B ^ C) & ~A
+    // (~A | ~B | C) & (~(A & C) | B) --> ~((B ^ C) & A)
+
+    // (~(A | B) & C) | (~A & ~C & B) --> (B ^ C) & ~A
+    // (~(A & B) | C) & (~A | ~C | B) --> ~((B ^ C) & A)
+    // (~A & ~B & C) | (~A & ~C & B) --> (B ^ C) & ~A
+    // (~A | ~B | C) & (~A | ~C | B) --> ~((B ^ C) & A)
     if (matchNotOrAnd(Op1, m_Specific(A), m_Specific(C), m_Specific(B), Dummy,
-                      true)) {
+                      Y, Dummy, true)) {
+      NotA = NotA ? NotA : Y;
       Value *Xor = Builder.CreateXor(B, C);
       return (Opcode == Instruction::Or)
-                 ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(A))
+                 ? BinaryOperator::CreateAnd(Xor,
+                                             NotA ? NotA : Builder.CreateNot(A))
                  : BinaryOperator::CreateNot(Builder.CreateAnd(Xor, A));
     }
 
     // (~(A | B) & C) | (~(B | C) & A) --> (A ^ C) & ~B
     // (~(A & B) | C) & (~(B & C) | A) --> ~((A ^ C) & B)
+    // (~A & ~B & C) | (~(B | C) & A) --> (A ^ C) & ~B
+    // (~A | ~B | C) & (~(B & C) | A) --> ~((A ^ C) & B)
+
+    // (~(A | B) & C) | (~B & ~C & A) --> (A ^ C) & ~B
+    // (~(A & B) | C) & (~B | ~C | A) --> ~((A ^ C) & B)
+    // (~A & ~B & C) | (~B & ~C & A) --> (A ^ C) & ~B
+    // (~A | ~B | C) & (~B | ~C | A) --> ~((A ^ C) & B)
     if (matchNotOrAnd(Op1, m_Specific(B), m_Specific(C), m_Specific(A), Dummy,
-                      true)) {
+                      Y, Dummy, true)) {
+      NotB = NotB ? NotB : Y;
       Value *Xor = Builder.CreateXor(A, C);
       return (Opcode == Instruction::Or)
-                 ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(B))
+                 ? BinaryOperator::CreateAnd(Xor,
+                                             NotB ? NotB : Builder.CreateNot(B))
                  : BinaryOperator::CreateNot(Builder.CreateAnd(Xor, B));
     }
 
     // (~(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(
+    if (X && 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 (match(Op1, m_OneUse(m_Not(m_OneUse(
+    if (X && 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));
 
     // (~(A | B) & C) | ~(C | (A ^ B)) --> ~((A | B) & (C | (A ^ B)))
     // Note, the pattern with swapped and/or is not handled because the
     // result is more undefined than a source:
     // (~(A & B) | C) & ~(C & (A ^ B)) --> (A ^ B ^ C) | ~(A | C) is invalid.
-    if (Opcode == Instruction::Or && Op0->hasOneUse() &&
+    if (X && Opcode == Instruction::Or && Op0->hasOneUse() &&
         match(Op1, m_OneUse(m_Not(m_CombineAnd(
                        m_Value(Y),
                        m_c_BinOp(Opcode, m_Specific(C),
                                  m_c_Xor(m_Specific(A), m_Specific(B)))))))) {
       // X = ~(A | B)
       // Y = (C | (A ^ B)
       Value *Or = cast<BinaryOperator>(X)->getOperand(0);
       return BinaryOperator::CreateNot(Builder.CreateAnd(Or, Y));

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

;
   %or1 = or i32 %not1, %c
   %and2 = and i32 %a, %c
   %not2 = xor i32 %and2, -1
   %or2 = or i32 %not2, %d
   %and3 = and i32 %or1, %or2
   ret i32 %and3
 }
 
+; (~a & ~b & c) | (b & ~(a | c)) --> ~a & (b ^ c)
+
+define i32 @not_and_not_and_and_or(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and3, %and2
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %notb, %nota
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %c
+  %and2 = and i32 %and1, %notb
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute4(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute4(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %c, %a
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute5(i32 %a, i32 %b0, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute5(
+; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %b, %not1
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+; (~a & ~b & c) | (a & ~(b | c)) --> ~b & (a ^ c)
+
+define i32 @not_and_not_and_and_or_commute6(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute6(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTB]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %a
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute7(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute7(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTB]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %a
+  %or3 = or i32 %and3, %and2
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute8(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute8(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTB]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %notb, %nota
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %a
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute9(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute9(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %notb, %c
+  %and2 = and i32 %and1, %nota
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %a
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute10(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute10(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTB]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %c, %b
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %a
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute11(i32 %a0, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute11(
+; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0:%.*]]
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTB]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %a, %not1
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %or3
+}
+
+; (~a & ~b & c) | (b & ~a & ~c) --> ~a & (b ^ c)
+
+define i32 @not_and_not_and_and_or_commute12(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute12(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %and3 = and i32 %nota, %notc
+  %and4 = and i32 %and3, %b
+  %or3 = or i32 %and2, %and4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute13(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute13(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTB]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %and3 = and i32 %notb, %notc
+  %and4 = and i32 %and3, %a
+  %or3 = or i32 %and2, %and4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_commute14(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_commute14(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %and3 = and i32 %notc, %nota
+  %and4 = and i32 %and3, %b
+  %or3 = or i32 %and4, %and2
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_use1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_use1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[NOT1]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[AND3]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[AND3]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %and3)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_use2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_use2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[NOTA]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_use3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_use3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[NOT1]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[AND3]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND3]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %and1)
+  call void @use(i32 %and3)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_use4(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_use4(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[NOT1]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[AND3]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[AND3]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %or1 = or i32 %a, %c
+  %not1 = xor i32 %or1, -1
+  %and3 = and i32 %not1, %b
+  %or3 = or i32 %and2, %and3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %and2)
+  call void @use(i32 %and3)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_use5(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_use5(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[AND4:%.*]] = and i32 [[AND3]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[AND4]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    call void @use(i32 [[AND3]])
+; CHECK-NEXT:    call void @use(i32 [[AND4]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %and3 = and i32 %nota, %notc
+  %and4 = and i32 %and3, %b
+  %or3 = or i32 %and2, %and4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  call void @use(i32 %and3)
+  call void @use(i32 %and4)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_use6(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_use6(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[AND4:%.*]] = and i32 [[AND3]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[AND4]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    call void @use(i32 [[AND3]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %and3 = and i32 %nota, %notc
+  %and4 = and i32 %and3, %b
+  %or3 = or i32 %and2, %and4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  call void @use(i32 %and3)
+  ret i32 %or3
+}
+
+define i32 @not_and_not_and_and_or_use7(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_not_and_and_or_use7(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[AND4:%.*]] = and i32 [[AND3]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[AND4]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    call void @use(i32 [[AND4]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %and1 = and i32 %nota, %notb
+  %and2 = and i32 %and1, %c
+  %and3 = and i32 %nota, %notc
+  %and4 = and i32 %and3, %b
+  %or3 = or i32 %and2, %and4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  call void @use(i32 %and4)
+  ret i32 %or3
+}
+
+; (~a | ~b | c) & (b | ~(a & c)) --> ~((b ^ c) & a)
+
+define i32 @not_or_not_or_or_and(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or3, %or2
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %notb, %nota
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %c
+  %or2 = or i32 %or1, %notb
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute4(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute4(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %c, %a
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute5(i32 %a, i32 %b0, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute5(
+; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %b, %not1
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+; (~a | ~b | c) & (a | ~(b & c)) --> ~((a ^ c) & b)
+
+define i32 @not_or_not_or_or_and_commute6(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute6(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %b, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %a
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute7(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute7(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C:%.*]], [[A]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %b, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %a
+  %and3 = and i32 %or3, %or2
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute8(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute8(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %notb, %nota
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %b, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %a
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute9(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute9(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %notb, %c
+  %or2 = or i32 %or1, %nota
+  %and1 = and i32 %b, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %a
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute10(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute10(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %c, %b
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %a
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute11(i32 %a0, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute11(
+; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0:%.*]]
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %b, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %a, %not1
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  ret i32 %and3
+}
+
+; (~a | ~b | c) & (b | ~a | ~c) --> ~((b ^ c) & a)
+
+define i32 @not_or_not_or_or_and_commute12(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute12(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %or3 = or i32 %nota, %notc
+  %or4 = or i32 %or3, %b
+  %and3 = and i32 %or2, %or4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute13(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute13(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %or3 = or i32 %notb, %notc
+  %or4 = or i32 %or3, %a
+  %and3 = and i32 %or2, %or4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_commute14(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_commute14(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %or3 = or i32 %notc, %nota
+  %or4 = or i32 %or3, %b
+  %and3 = and i32 %or4, %or2
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_use1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_use1(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[NOT1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR2]], [[OR3]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[OR3]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  call void @use(i32 %or3)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_use2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_use2(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_use3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_use3(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[NOT1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR2]], [[OR3]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR3]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %or1)
+  call void @use(i32 %or3)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_use4(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_use4(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[NOT1]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR2]], [[OR3]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[OR3]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %and1 = and i32 %a, %c
+  %not1 = xor i32 %and1, -1
+  %or3 = or i32 %not1, %b
+  %and3 = and i32 %or2, %or3
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %or2)
+  call void @use(i32 %or3)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_use5(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_use5(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[OR3]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR2]], [[OR4]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    call void @use(i32 [[OR3]])
+; CHECK-NEXT:    call void @use(i32 [[OR4]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %or3 = or i32 %nota, %notc
+  %or4 = or i32 %or3, %b
+  %and3 = and i32 %or2, %or4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  call void @use(i32 %or3)
+  call void @use(i32 %or4)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_use6(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_use6(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[OR3]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR2]], [[OR4]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    call void @use(i32 [[OR3]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %or3 = or i32 %nota, %notc
+  %or4 = or i32 %or3, %b
+  %and3 = and i32 %or2, %or4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  call void @use(i32 %or3)
+  ret i32 %and3
+}
+
+define i32 @not_or_not_or_or_and_use7(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_not_or_or_and_use7(
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[NOTB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[NOTC:%.*]] = xor i32 [[C:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOTA]], [[NOTB]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[NOTA]], [[NOTC]]
+; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[OR3]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR2]], [[OR4]]
+; CHECK-NEXT:    call void @use(i32 [[NOTA]])
+; CHECK-NEXT:    call void @use(i32 [[NOTB]])
+; CHECK-NEXT:    call void @use(i32 [[NOTC]])
+; CHECK-NEXT:    call void @use(i32 [[OR4]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %nota = xor i32 %a, -1
+  %notb = xor i32 %b, -1
+  %notc = xor i32 %c, -1
+  %or1 = or i32 %nota, %notb
+  %or2 = or i32 %or1, %c
+  %or3 = or i32 %nota, %notc
+  %or4 = or i32 %or3, %b
+  %and3 = and i32 %or2, %or4
+  call void @use(i32 %nota)
+  call void @use(i32 %notb)
+  call void @use(i32 %notc)
+  call void @use(i32 %or4)
+  ret i32 %and3
+}
+
 ; (b & ~(a | c)) | ~(a | b) --> ~((b & c) | a)
 
 define i32 @or_and_not_not(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @or_and_not_not(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[OR3]]