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

[rampitec]

Summary

This handles expressions:

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

and swapped case:

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

The expression (~(a | b) & c) | ~((a | b) | c) is just an
(~x & c) | ~(x | c) and will be simplified without this
patch but two cases above need reassociation.

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

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

[rampitec]

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

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

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

[rampitec]

Added swapped case

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

[rampitec]

Rebased.

[spatel]

As discussed in D114462, I noticed a pair of missing 'xor' simplifications based on these patterns, so I added those with:
892648b18a8c
b326c058146f

So we probably want to add some or all of these tests under "test/Transforms/PhaseOrdering" to see if these are reduced with the default -O2/-O3 pipelines or some combination of specific passes (-reassociate, -gvn, -instcombine).

This patch could also be moved to -instsimplify if it is still needed. But I think that would really be covering up a shortcoming of -reassociate. That pass should find the common 'or' or 'and' value in these patterns?

[rampitec]

In D113216#3151315, @spatel wrote:

As discussed in D114462, I noticed a pair of missing 'xor' simplifications based on these patterns, so I added those with:
892648b18a8c
b326c058146f

So we probably want to add some or all of these tests under "test/Transforms/PhaseOrdering" to see if these are reduced with the default -O2/-O3 pipelines or some combination of specific passes (-reassociate, -gvn, -instcombine).

I have moved these tests into new Transforms/PhaseOrdering/reassociate-gvn-bdce.ll. That is a combination of -reassociate -gvn -bdce which now handles it.

This patch could also be moved to -instsimplify if it is still needed. But I think that would really be covering up a shortcoming of -reassociate. That pass should find the common 'or' or 'and' value in these patterns?

I am dropping it, these cases are already handled by your D114462. The case (~A & ~B & C) | ~(A | B | C) --> ~(A | B) is not, but just reassociation will not help, it needs to be combined with demorganing and use analysis. It will need a separate patch, however.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::narrowMaskedBinOp(BinaryOperator &And) {
   Value *NewC = ConstantExpr::getTrunc(C, X->getType());
   Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
                                          : Builder.CreateBinOp(Opc, X, NewC);
   return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
 }
 
 /// Try folding relatively complex patterns for both And and Or operations
 /// with all And and Or swapped.
-static Instruction *foldComplexAndOrPatterns(BinaryOperator &I,
-                                             InstCombiner::BuilderTy &Builder) {
+Instruction *InstCombinerImpl::foldComplexAndOrPatterns(BinaryOperator &I) {
   const Instruction::BinaryOps Opcode = I.getOpcode();
   assert(Opcode == Instruction::And || Opcode == Instruction::Or);
 
   // Flip the logic operation.
   const Instruction::BinaryOps FlippedOpcode =
       (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (Op0->hasOneUse() &&
         return BinaryOperator::CreateNot(Builder.CreateAnd(AndOr, Z));
       } else if (X->hasOneUse() && AndOr->hasOneUse() && Z->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)
+    // (~(A | B) & C) | ~(B | (A | C)) --> ~(A | B)
+    // (~(A & B) | C) & ~(A & (B & C)) --> ~(A & B)
+    // (~(A & B) | C) & ~(B & (A & C)) --> ~(A & B)
+    if (match(Op1, m_Not(m_c_BinOp(
+                       Opcode, m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)),
+                       m_Specific(A)))) ||
+        match(Op1, m_Not(m_c_BinOp(
+                       Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)),
+                       m_Specific(B)))))
+      return replaceInstUsesWith(I, X);
   }
 
   return nullptr;
 }
 
 // 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) {
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   // Do this before using distributive laws to catch simple and/or/not patterns.
   if (Instruction *Xor = foldAndToXor(I, Builder))
     return Xor;
 
-  if (Instruction *X = foldComplexAndOrPatterns(I, Builder))
+  if (Instruction *X = foldComplexAndOrPatterns(I))
     return X;
 
   // (A|B)&(A|C) -> A|(B&C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyBSwap(I, Builder))
     return replaceInstUsesWith(I, V);
Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   // Do this before using distributive laws to catch simple and/or/not patterns.
   if (Instruction *Xor = foldOrToXor(I, Builder))
     return Xor;
 
-  if (Instruction *X = foldComplexAndOrPatterns(I, Builder))
+  if (Instruction *X = foldComplexAndOrPatterns(I))
     return X;
 
   // (A&B)|(A&C) -> A&(B|C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyBSwap(I, Builder))
     return replaceInstUsesWith(I, V);

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
 
   // Optimize one of these forms:
   //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
   //   or i1 Op, SI  / select i1 Op, i1 true, i1 SI  (if IsAnd = false)
   // into simplier select instruction using isImpliedCondition.
   Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
                                                  bool IsAnd);
 
+  /// Try folding relatively complex patterns for both And and Or operations
+  /// with all And and Or swapped.
+  Instruction *foldComplexAndOrPatterns(BinaryOperator &I);
+
 public:
   /// Inserts an instruction \p New before instruction \p Old
   ///
   /// Also adds the new instruction to the worklist and returns \p New so that
   /// it is suitable for use as the return from the visitation patterns.
   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
     assert(New && !New->getParent() &&
            "New instruction already inserted into a basic block!");

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

;
   ret i32 %and2
 }
 
 ; (~(a | b) & c) | ~(a | (b | c)) -> ~(a | b)
 ; (~(a | b) & c) | ~(b | (a | c)) -> ~(a | b)
 
 define i32 @not_or_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %a
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %b, %a
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %not2, %c
   %or4 = or i32 %and2, %not1
   ret i32 %or4
 }
 
 define i32 @not_or_and_or_not_or_or_commute1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute1(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %a, %c
   %or2 = or i32 %or1, %b
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %b, %a
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %not2, %c
   %or4 = or i32 %and2, %not1
   ret i32 %or4
 }
 
 define i32 @not_or_and_or_not_or_or_commute2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute2(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %c, %b
   %or2 = or i32 %or1, %a
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %b, %a
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %not2, %c
   %or4 = or i32 %and2, %not1
   ret i32 %or4
 }
 
 define i32 @not_or_and_or_not_or_or_commute3(i32 %a0, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute3(
 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[OR1]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[A]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
   %or1 = or i32 %b, %c
   %or2 = or i32 %a, %or1
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %a, %b
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %not2, %c
   %or4 = or i32 %and2, %not1
   ret i32 %or4
 }
 
 define i32 @not_or_and_or_not_or_or_commute4(i32 %a, i32 %b0, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute4(
 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[B]], [[OR1]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
   %or1 = or i32 %a, %c
   %or2 = or i32 %b, %or1
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %b, %a
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %not2, %c
   %or4 = or i32 %and2, %not1
   ret i32 %or4
 }
 
 define i32 @not_or_and_or_not_or_or_commute5(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_commute5(
-; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[C]], [[NOT2]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %or1 = or i32 %c, %a
   %or2 = or i32 %or1, %b
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %b, %a
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %c, %not2
   %or4 = or i32 %and2, %not1
   ret i32 %or4
 }
 
 define i32 @not_or_and_or_not_or_or_use1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_use1(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %b, %c
   %or2 = or i32 %or1, %a
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %b, %a
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %not2, %c
   %or4 = or i32 %and2, %not1
   call void @use(i32 %not1)
   ret i32 %or4
 }
 
 define i32 @not_or_and_or_not_or_or_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_and_or_not_or_or_use2(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[B:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[OR4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %or1 = or i32 %a, %c
   %or2 = or i32 %or1, %b
   %not1 = xor i32 %or2, -1
   %or3 = or i32 %b, %a
   %not2 = xor i32 %or3, -1
   %and2 = and i32 %not2, %c
   %or4 = or i32 %and2, %not1
   call void @use(i32 %not1)
   ret i32 %or4
 }
 
 ; (~(a & b) | c) & ~(a & (b & c)) -> ~(a & b)
 ; (~(a & b) | c) & ~(b & (a & c)) -> ~(a & b)
 
 define i32 @not_and_or_and_not_and_and(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %a
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %b, %a
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %not2, %c
   %and4 = and i32 %or2, %not1
   ret i32 %and4
 }
 
 define i32 @not_and_or_and_not_and_and_commute1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute1(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %a, %c
   %and2 = and i32 %and1, %b
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %b, %a
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %not2, %c
   %and4 = and i32 %or2, %not1
   ret i32 %and4
 }
 
 define i32 @not_and_or_and_not_and_and_commute2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute2(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %c, %b
   %and2 = and i32 %and1, %a
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %b, %a
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %not2, %c
   %and4 = and i32 %or2, %not1
   ret i32 %and4
 }
 
 define i32 @not_and_or_and_not_and_and_commute3(i32 %a0, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute3(
 ; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[A0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[AND1]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[A]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %a = sdiv i32 42, %a0 ; thwart complexity-based canonicalization
   %and1 = and i32 %b, %c
   %and2 = and i32 %a, %and1
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %a, %b
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %not2, %c
   %and4 = and i32 %or2, %not1
   ret i32 %and4
 }
 
 define i32 @not_and_or_and_not_and_and_commute4(i32 %a, i32 %b0, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute4(
 ; CHECK-NEXT:    [[B:%.*]] = sdiv i32 42, [[B0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[B]], [[AND1]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %b = sdiv i32 42, %b0 ; thwart complexity-based canonicalization
   %and1 = and i32 %a, %c
   %and2 = and i32 %b, %and1
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %b, %a
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %not2, %c
   %and4 = and i32 %or2, %not1
   ret i32 %and4
 }
 
 define i32 @not_and_or_and_not_and_and_commute5(i32 %a, i32 %b, i32 %c0) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_commute5(
-; CHECK-NEXT:    [[C:%.*]] = sdiv i32 42, [[C0:%.*]]
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B:%.*]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[C]], [[NOT2]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %c = sdiv i32 42, %c0 ; thwart complexity-based canonicalization
   %and1 = and i32 %c, %a
   %and2 = and i32 %and1, %b
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %b, %a
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %c, %not2
   %and4 = and i32 %or2, %not1
   ret i32 %and4
 }
 
 define i32 @not_and_or_and_not_and_and_use1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_use1(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %b, %c
   %and2 = and i32 %and1, %a
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %b, %a
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %not2, %c
   %and4 = and i32 %or2, %not1
   call void @use(i32 %not1)
   ret i32 %and4
 }
 
 define i32 @not_and_or_and_not_and_and_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_or_and_not_and_and_use2(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[B:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND3]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[C]]
-; CHECK-NEXT:    [[AND4:%.*]] = xor i32 [[AND2]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
-; CHECK-NEXT:    ret i32 [[AND4]]
+; CHECK-NEXT:    ret i32 [[NOT2]]
 ;
   %and1 = and i32 %a, %c
   %and2 = and i32 %and1, %b
   %not1 = xor i32 %and2, -1
   %and3 = and i32 %b, %a
   %not2 = xor i32 %and3, -1
   %or2 = or i32 %not2, %c
   %and4 = and i32 %or2, %not1
   call void @use(i32 %not1)
   ret i32 %and4
 }