[InstCombine] Unfold masked merge with constant mask

[lebedev.ri]

Summary

As discussed in D45733, we want to do this in InstCombine.

https://rise4fun.com/Alive/LGk

[lebedev.ri]

Rebased.

[lebedev.ri]

• Rebased.
• This differential is the one to review, it has no unmerged deps/prerequisites.

[xbolva00]

Not related to this patch exactly but since you work in this area... maybe you can check this too?
https://godbolt.org/g/wksfqb

[lebedev.ri]

In D45867#1082079, @xbolva00 wrote:

Not related to this patch exactly but since you work in this area... maybe you can check this too?
https://godbolt.org/g/wksfqb

That particular example should be handled by dead code elimination pass i guess,
because it is literally optimized down to return 0;,
since it only reads global uint32_t b; once, and ultimately does nothing with that.

But, i have zero clues how it should be done.

[xbolva00]

In D45867#1082081, @lebedev.ri wrote:

In D45867#1082079, @xbolva00 wrote:

Not related to this patch exactly but since you work in this area... maybe you can check this too?
https://godbolt.org/g/wksfqb

That particular example should be handled by dead code elimination pass i guess,
because it is literally optimized down to return 0;,
since it only reads global uint32_t b; once, and ultimately does nothing with that.

But, i have zero clues how it should be done.

It is interesting, since even if we dont use "b", just leave it as "uint32_t a = 5;", the code is not eliminated since optimizer may think it could be infinite loop (?) (cc @chandlerc , @spatel )

[lebedev.ri]

In D45867#1082082, @xbolva00 wrote:

In D45867#1082081, @lebedev.ri wrote:

In D45867#1082079, @xbolva00 wrote:

Not related to this patch exactly but since you work in this area... maybe you can check this too?
https://godbolt.org/g/wksfqb

That particular example should be handled by dead code elimination pass i guess,
because it is literally optimized down to return 0;,
since it only reads global uint32_t b; once, and ultimately does nothing with that.

But, i have zero clues how it should be done.

It is interesting, since even if we dont use "b", just leave it as "uint32_t a = 5;", the code is not eliminated since optimizer may think it could be infinite loop (?) (cc @chandlerc , @spatel )

You probably want to move that to a bugzilla issue, as you have noted yourself, this is completely unrelated from the patch a hand.

[spatel]

LGTM - see inline comments.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2421–2423 ↗

(On Diff #144454)

We should state our reasoning here - because I know I won't remember for long. :)

So something like:
We can canonicalize by swapping the final xor operand to eliminate the 'not' of the mask.
If M is a constant, we transform to 'and' / 'or' ops because that shortens the dependency chain and improves analysis.

2447 ↗

(On Diff #144454)

iC -> NotC

[lebedev.ri]

@spatel thank you for the review!

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2433 ↗

(On Diff #144454)

I'm wondering if by simply capturing M here we miss some opportunities where
this first matched M does not satisfy any of these following checks (inverted/constant).

But i'm also not sure how to squeeze that into this one match(), in particular
i don't see how to know which of the matches is the real match, and which one is
stale pointer from the previous partial match.

llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
       }
     }
   }
 
   return nullptr;
 }
 
 /// If we have a masked merge, in the canonical form of:
+/// (assuming that A only has one use.)
 ///   |        A  |  |B|
 ///   ((x ^ y) & M) ^ y
 ///    |  D  |
 /// * If M is inverted:
 ///      |  D  |
 ///     ((x ^ y) & ~M) ^ y
-///   If A has one use, and, we want to canonicalize it to non-inverted mask:
+///   We can canonicalize by swapping the final xor operand
+///   to eliminate the 'not' of the mask.
 ///     ((x ^ y) & M) ^ x
+/// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
+///   because that shortens the dependency chain and improves analysis:
+///     (x & M) | (y & ~M)
 static Instruction *visitMaskedMerge(BinaryOperator &I,
                                      InstCombiner::BuilderTy &Builder) {
   Value *B, *X, *D;
   Value *M;
   if (!match(&I, m_c_Xor(m_Value(B),
                          m_OneUse(m_c_And(
                              m_CombineAnd(m_c_Xor(m_Deferred(B), m_Value(X)),
                                           m_Value(D)),
                              m_Value(M))))))
     return nullptr;
 
   Value *NotM;
   if (match(M, m_Not(m_Value(NotM)))) {
     // De-invert the mask and swap the value in B part.
     Value *NewA = Builder.CreateAnd(D, NotM);
     return BinaryOperator::CreateXor(NewA, X);
   }
 
+  Constant *C;
+  if (D->hasOneUse() && match(M, m_Constant(C))) {
+    // Unfold.
+    Value *LHS = Builder.CreateAnd(X, C);
+    Value *NotC = Builder.CreateNot(C);
+    Value *RHS = Builder.CreateAnd(B, NotC);
+    return BinaryOperator::CreateOr(LHS, RHS);
+  }
+
   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 *InstCombiner::visitXor(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);

llvm/trunk/test/Transforms/InstCombine/unfold-masked-merge-with-const-mask-scalar.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; If we have a masked merge, in the form of: (M is constant)
 ;   ((x ^ y) & M) ^ y
 ; Unfold it to
 ;   (x & M) | (y & ~M)
 
 define i4 @scalar0 (i4 %x, i4 %y) {
 ; CHECK-LABEL: @scalar0(
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], 1
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[X:%.*]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[Y:%.*]], -2
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %n0 = xor i4 %x, %y
   %n1 = and i4 %n0, 1
   %r  = xor i4 %n1, %y
   ret i4 %r
 }
 
 define i4 @scalar1 (i4 %x, i4 %y) {
 ; CHECK-LABEL: @scalar1(
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[X:%.*]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[Y:%.*]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %n0 = xor i4 %x, %y
   %n1 = and i4 %n0, -2
   %r  = xor i4 %n1, %y
   ret i4 %r
 }
 

 ; Commutativity
 ; ============================================================================ ;
 
 ; Used to make sure that the IR complexity sorting does not interfere.
 declare i4 @gen4()
 
 define i4 @c_1_0_0 (i4 %x, i4 %y) {
 ; CHECK-LABEL: @c_1_0_0(
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[X:%.*]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[Y:%.*]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %n0 = xor i4 %y, %x ; swapped order
   %n1 = and i4 %n0, -2
   %r  = xor i4 %n1, %y
   ret i4 %r
 }
 
 define i4 @c_0_1_0 (i4 %x, i4 %y) {
 ; CHECK-LABEL: @c_0_1_0(
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[N1]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[Y:%.*]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[X:%.*]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %n0 = xor i4 %x, %y
   %n1 = and i4 %n0, -2
   %r  = xor i4 %n1, %x ; %x instead of %y
   ret i4 %r
 }
 
 define i4 @c_0_0_1 () {
 ; CHECK-LABEL: @c_0_0_1(
 ; CHECK-NEXT:    [[X:%.*]] = call i4 @gen4()
 ; CHECK-NEXT:    [[Y:%.*]] = call i4 @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[X]], [[Y]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[Y]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[X]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[Y]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %x  = call i4 @gen4()
   %y  = call i4 @gen4()
   %n0 = xor i4 %x, %y
   %n1 = and i4 %n0, -2
   %r  = xor i4 %y, %n1 ; swapped order
   ret i4 %r
 }
 
 define i4 @c_1_1_0 (i4 %x, i4 %y) {
 ; CHECK-LABEL: @c_1_1_0(
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[N1]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[Y:%.*]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[X:%.*]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %n0 = xor i4 %y, %x ; swapped order
   %n1 = and i4 %n0, -2
   %r  = xor i4 %n1, %x ; %x instead of %y
   ret i4 %r
 }
 
 define i4 @c_1_0_1 (i4 %x) {
 ; CHECK-LABEL: @c_1_0_1(
 ; CHECK-NEXT:    [[Y:%.*]] = call i4 @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[Y]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[X:%.*]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[Y]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %y  = call i4 @gen4()
   %n0 = xor i4 %y, %x ; swapped order
   %n1 = and i4 %n0, -2
   %r  = xor i4 %y, %n1 ; swapped order
   ret i4 %r
 }
 
 define i4 @c_0_1_1 (i4 %y) {
 ; CHECK-LABEL: @c_0_1_1(
 ; CHECK-NEXT:    [[X:%.*]] = call i4 @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[X]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[Y:%.*]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[X]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %x  = call i4 @gen4()
   %n0 = xor i4 %x, %y
   %n1 = and i4 %n0, -2
   %r  = xor i4 %x, %n1 ; swapped order, %x instead of %y
   ret i4 %r
 }
 
 define i4 @c_1_1_1 () {
 ; CHECK-LABEL: @c_1_1_1(
 ; CHECK-NEXT:    [[X:%.*]] = call i4 @gen4()
 ; CHECK-NEXT:    [[Y:%.*]] = call i4 @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor i4 [[Y]], [[X]]
-; CHECK-NEXT:    [[N1:%.*]] = and i4 [[N0]], -2
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[X]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i4 [[Y]], -2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i4 [[X]], 1
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %x  = call i4 @gen4()
   %y  = call i4 @gen4()
   %n0 = xor i4 %y, %x ; swapped order
   %n1 = and i4 %n0, -2
   %r  = xor i4 %x, %n1 ; swapped order, %x instead of %y
   ret i4 %r

llvm/trunk/test/Transforms/InstCombine/unfold-masked-merge-with-const-mask-vector.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; If we have a masked merge, in the form of: (M is constant)
 ;   ((x ^ y) & M) ^ y
 ; Unfold it to
 ;   (x & M) | (y & ~M)
 
 define <2 x i4> @splat (<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @splat(
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[Y:%.*]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %x, %y
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %n1, %y
   ret <2 x i4> %r
 }
 
 define <3 x i4> @splat_undef (<3 x i4> %x, <3 x i4> %y) {
 ; CHECK-LABEL: @splat_undef(
-; CHECK-NEXT:    [[N0:%.*]] = xor <3 x i4> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <3 x i4> [[N0]], <i4 -2, i4 undef, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <3 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <3 x i4> [[X:%.*]], <i4 -2, i4 undef, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i4> [[Y:%.*]], <i4 1, i4 undef, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <3 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <3 x i4> [[R]]
 ;
   %n0 = xor <3 x i4> %x, %y
   %n1 = and <3 x i4> %n0, <i4 -2, i4 undef, i4 -2>
   %r  = xor <3 x i4> %n1, %y
   ret <3 x i4> %r
 }
 
 define <2 x i4> @nonsplat (<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @nonsplat(
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 1>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], <i4 -2, i4 1>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[Y:%.*]], <i4 1, i4 -2>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %x, %y
   %n1 = and <2 x i4> %n0, <i4 -2, i4 1>
   %r  = xor <2 x i4> %n1, %y
   ret <2 x i4> %r
 }
 
;
   %n0 = xor <2 x i4> %x, <i4 14, i4 14> ; %x
   %n1 = and <2 x i4> %n0, <i4 1, i4 1>
   %r = xor <2 x i4> %n1, <i4 14, i4 14>
   ret <2 x i4> %r
 }
 
 define <2 x i4> @in_constant_varx_14_nonsplat(<2 x i4> %x, <2 x i4> %mask) {
 ; CHECK-LABEL: @in_constant_varx_14_nonsplat(
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[X:%.*]], <i4 -2, i4 7>
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 1, i4 1>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], <i4 -2, i4 7>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], <i4 -2, i4 6>
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %x, <i4 14, i4 7> ; %x
   %n1 = and <2 x i4> %n0, <i4 1, i4 1>
   %r = xor <2 x i4> %n1, <i4 14, i4 7>
   ret <2 x i4> %r
 }
 
 define <3 x i4> @in_constant_varx_14_undef(<3 x i4> %x, <3 x i4> %mask) {
 ; CHECK-LABEL: @in_constant_varx_14_undef(
-; CHECK-NEXT:    [[N0:%.*]] = xor <3 x i4> [[X:%.*]], <i4 -2, i4 undef, i4 7>
-; CHECK-NEXT:    [[N1:%.*]] = and <3 x i4> [[N0]], <i4 1, i4 undef, i4 1>
-; CHECK-NEXT:    [[R:%.*]] = xor <3 x i4> [[N1]], <i4 -2, i4 undef, i4 7>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <3 x i4> [[X:%.*]], <i4 1, i4 undef, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <3 x i4> [[TMP1]], <i4 -2, i4 undef, i4 6>
 ; CHECK-NEXT:    ret <3 x i4> [[R]]
 ;
   %n0 = xor <3 x i4> %x, <i4 14, i4 undef, i4 7> ; %x
   %n1 = and <3 x i4> %n0, <i4 1, i4 undef, i4 1>
   %r = xor <3 x i4> %n1, <i4 14, i4 undef, i4 7>
   ret <3 x i4> %r
 }
 
;
   %n0 = xor <2 x i4> %y, <i4 14, i4 14> ; %x
   %n1 = and <2 x i4> %n0, <i4 1, i4 1>
   %r = xor <2 x i4> %n1, %y
   ret <2 x i4> %r
 }
 
 define <2 x i4> @in_constant_14_vary_nonsplat(<2 x i4> %y, <2 x i4> %mask) {
 ; CHECK-LABEL: @in_constant_14_vary_nonsplat(
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[Y:%.*]], <i4 -2, i4 7>
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 1, i4 1>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[Y:%.*]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], <i4 0, i4 1>
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %y, <i4 14, i4 7> ; %x
   %n1 = and <2 x i4> %n0, <i4 1, i4 1>
   %r = xor <2 x i4> %n1, %y
   ret <2 x i4> %r
 }
 
 define <3 x i4> @in_constant_14_vary_undef(<3 x i4> %y, <3 x i4> %mask) {
 ; CHECK-LABEL: @in_constant_14_vary_undef(
-; CHECK-NEXT:    [[N0:%.*]] = xor <3 x i4> [[Y:%.*]], <i4 -2, i4 undef, i4 7>
-; CHECK-NEXT:    [[N1:%.*]] = and <3 x i4> [[N0]], <i4 1, i4 undef, i4 1>
-; CHECK-NEXT:    [[R:%.*]] = xor <3 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <3 x i4> [[Y:%.*]], <i4 -2, i4 undef, i4 -2>
+; CHECK-NEXT:    [[R:%.*]] = or <3 x i4> [[TMP1]], <i4 0, i4 undef, i4 1>
 ; CHECK-NEXT:    ret <3 x i4> [[R]]
 ;
   %n0 = xor <3 x i4> %y, <i4 14, i4 undef, i4 7> ; %x
   %n1 = and <3 x i4> %n0, <i4 1, i4 undef, i4 1>
   %r = xor <3 x i4> %n1, %y
   ret <3 x i4> %r
 }
 
 ; ============================================================================ ;
 ; Commutativity
 ; ============================================================================ ;
 
 ; Used to make sure that the IR complexity sorting does not interfere.
 declare <2 x i4> @gen4()
 
 define <2 x i4> @c_1_0_0 (<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @c_1_0_0(
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[Y:%.*]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %y, %x ; swapped order
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %n1, %y
   ret <2 x i4> %r
 }
 
 define <2 x i4> @c_0_1_0 (<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @c_0_1_0(
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[Y:%.*]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[X:%.*]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %x, %y
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %n1, %x ; %x instead of %y
   ret <2 x i4> %r
 }
 
 define <2 x i4> @c_0_0_1 () {
 ; CHECK-LABEL: @c_0_0_1(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i4> @gen4()
 ; CHECK-NEXT:    [[Y:%.*]] = call <2 x i4> @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[X]], [[Y]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[Y]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[Y]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %x  = call <2 x i4> @gen4()
   %y  = call <2 x i4> @gen4()
   %n0 = xor <2 x i4> %x, %y
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %y, %n1 ; swapped order
   ret <2 x i4> %r
 }
 
 define <2 x i4> @c_1_1_0 (<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @c_1_1_0(
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[N1]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[Y:%.*]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[X:%.*]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %n0 = xor <2 x i4> %y, %x ; swapped order
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %n1, %x ; %x instead of %y
   ret <2 x i4> %r
 }
 
 define <2 x i4> @c_1_0_1 (<2 x i4> %x) {
 ; CHECK-LABEL: @c_1_0_1(
 ; CHECK-NEXT:    [[Y:%.*]] = call <2 x i4> @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[Y]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[Y]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %y  = call <2 x i4> @gen4()
   %n0 = xor <2 x i4> %y, %x ; swapped order
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %y, %n1 ; swapped order
   ret <2 x i4> %r
 }
 
 define <2 x i4> @c_0_1_1 (<2 x i4> %y) {
 ; CHECK-LABEL: @c_0_1_1(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i4> @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[X]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[Y:%.*]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[X]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %x  = call <2 x i4> @gen4()
   %n0 = xor <2 x i4> %x, %y
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %x, %n1 ; swapped order, %x instead of %y
   ret <2 x i4> %r
 }
 
 define <2 x i4> @c_1_1_1 () {
 ; CHECK-LABEL: @c_1_1_1(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i4> @gen4()
 ; CHECK-NEXT:    [[Y:%.*]] = call <2 x i4> @gen4()
-; CHECK-NEXT:    [[N0:%.*]] = xor <2 x i4> [[Y]], [[X]]
-; CHECK-NEXT:    [[N1:%.*]] = and <2 x i4> [[N0]], <i4 -2, i4 -2>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[X]], [[N1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[Y]], <i4 -2, i4 -2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i4> [[X]], <i4 1, i4 1>
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %x  = call <2 x i4> @gen4()
   %y  = call <2 x i4> @gen4()
   %n0 = xor <2 x i4> %y, %x ; swapped order
   %n1 = and <2 x i4> %n0, <i4 -2, i4 -2>
   %r  = xor <2 x i4> %x, %n1 ; swapped order, %x instead of %y
   ret <2 x i4> %r